const N = 1010;

let f = new Int32Array(N).fill(1);
let g = []; //g[i]:存放第i套拦截系统 当前拦截的最后一枚导弹高度（也就是当前接受的最低高度）

let buf = '';
process.stdin.on('readable', function () {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            let arr = getInputNums(line);
            let n = arr.length;
            let res = 0;
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < i; j++) {
                    if (arr[i] <= arr[j]) f[i] = Math.max(f[i], f[j] + 1); //不小于
                }
                res = Math.max(res, f[i]);
            }
            console.log(res);

            let cnt = 0; //拦截系统数
            for (let i = 0; i < n; i++) {
                let k = 1;
                while (k <= cnt && g[k] < arr[i]) k++; //贪心， 总是从数组下标小开始存最小的数，g[1] < g[2]
                g[k] = arr[i];
                if (k > cnt) cnt++;
            }
            console.log(cnt);
        }
    });
});