#include <bits/stdc++.h>

using namespace std;

int a[1001] = {0};
int f[1001] = {0};

#define INF 0x3f3f3f3f

int main() {
    //输入+输出重定向
    freopen("../1276.txt", "r", stdin);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //初始值
    int MAX = -INF;

    for (int i = 1; i <= n; i++) { //遍历每一个元素
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] > a[i] && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
            }
        }
        //将最小的dp[i]的值，记录到MIN里
        MAX = max(MAX, f[i]);
    }
    //输出MAX
    cout << MAX << endl;

    /*
    //输出dp
    for (int i = 1; i < n; i++) {
        cout << dp[i] << " ";
    }
    cout << endl;
    */
    //贪心策略（从头开始，如果发现数字在增长，就不管它，如果发现一样，或者变小了，则count++,最后到头时，需要补一个++）
    int count = 0;
    for (int i = 1; i < n; i++) {
        if (f[i] >= f[i + 1]) count++;
    }
    cout << count + 1 << endl;

    //关闭文件
    fclose(stdin);
    return 0;
}