思路证明:

注意这里：
$f$是一个非严格递减子序列，每次枚举到一个新的$q[i]$时，
会先遇到最大的小于$q[i]$的$f[k]$，然后更新$f[k] = q[i]$，
那么更新后的结果仍然是一个非严格递减序列

证明：
开始f为
$f[1] >= f[2] >= f[3] >= f[4] >= … >= f[cnt - 1] >= f[cnt] $
枚举到一个新的$q[i]$时,遍历$f$,假设$f[j]$是小于$q[i]$的最大的数,更新后$f[j] = q[i]$
对于前面，由于$f[j]$是小于$q[i]$最大的数,则$f[1~j-1]$都小于等于$f[j]$,则$f[1~j-1]$小于$q[i]$
对于后面，由于$f[j]$是小于$q[i]$最大的数,则$f[j+1~cnt]$都大于等于$q[i]$,
故更新后仍满足$f$是一个非严格递减序列

#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 1010;
int q[N], n = 1;
int b[N], gb;
int f[N];

int b_s(int l, int r, int x) {
    while(l < r) {
        int mid = l + r >> 1;
        if(b[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main()
{
    while(~scanf("%d", &q[n])) n++; 

    b[++gb] = q[n - 1];
    for(int i = n - 2; i >= 1; i--) {
        if(q[i] >= b[gb]) b[++gb] = q[i];
        else {
            int t = b_s(1, gb, q[i]);
            b[t] = q[i];
        }
    }

    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        int k = 1;
        while(k <= cnt && f[k] < q[i]) k++;
        if(k > cnt) f[++cnt] = q[i];
        else f[k] = q[i];
    }

    printf("%d\n%d", gb, cnt);

    return 0;
}