感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e3 + 10;
int n;
map<ll, int> mp;
set<ll> s;
void init(){
    ll val;
    while(scanf("%lld", &val)){
        s.insert(val); auto itm = s.lower_bound(val);
        if(s.begin() == itm){
            puts("无前驱 ");
            itm++; if(itm == s.end()) puts("无后驱"); else printf("后驱为%lld\n", *itm);
        }
        else{
            printf("前驱为%lld ", *prev(itm));
            itm++; if(itm == s.end()) puts("无后驱"); else printf("后驱为%lld\n", *itm);
        }
    }
}
int main(){
    //init();
    scanf("%d", &n);
    ll ans = 0, x; mp[inf] = -1; mp[-inf] = -1;
    s.insert(inf); s.insert(-inf);
    while(n--){
        scanf("%lld", &x);
        auto itm = s.lower_bound(x);
        mp[x] = max(mp[*prev(itm)], mp[*itm]) + 1;
        ans += mp[x];
        printf("%lld\n", ans);
        s.insert(x);
    }
    return 0;
}