1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>

using namespace std;

class Naszyjnik{
    public:
    int n;
    vector<int> korale;
    Naszyjnik(int n = 0){ init(n); };
    void init(int n_){
        n = n_;
        korale.assign(n+1, 0);
    }
    void add_koral(int i, int v){
        korale[i] = v;
    }

    void fill_max_sum_pref(vector<int>& M, vector<int>& SP){
        for(int i = 1; i <= n; i++){
            M[i] = max(M[i-1], korale[i]);
            SP[i] = SP[i-1];
            if( M[i] > M[i-1] ) SP[i]++;
        }
    }

    void fill_result_max_end(vector<int> &R, vector<int> &M){
        stack< pair<int, int> > KM; KM.push( {1e9, n+1} );
        for(int i = n; i >= 1; i--){
            while( korale[i] >= KM.top().first ) KM.pop();
            R[i] = R[ KM.top().second ] + 1;
            if( KM.top().second > n )  M[i] = korale[i];
            else                         M[i] = M[ KM.top().second ];
            KM.push( {korale[i], i} );
        }
    }

    int solve(){
        vector<int> max_to(n+1, 0);
        vector<int> sum_pref(n+1, 0);
        vector<int> result_from(n+1, 0);
        vector<int> max_at_end(n+1, 0);
        fill_max_sum_pref(max_to, sum_pref);
        fill_result_max_end(result_from, max_at_end);
        //for(int i = 1; i <= n; i++) cout << result_from[i] << " ";
        //cout << endl;
        int ans = 0; int l = 1e9;
        for(int i = 1; i <= n; i++){
            ans = max(ans, result_from[i]);
            if( max_to[i-1] <= max_at_end[i] ) continue;
            if( l == 1e9 ) l = i;
            while( l-1>=1 && max_to[l-1] > max_at_end[i] ) l--;
            //cout << "INTRESTING " << i << " " <<  result_from[i] << endl;
            //cout << l  << " "  << sum_pref[i-1] << " " << sum_pref[l-1] << endl;
            ans = max(ans, result_from[i] + sum_pref[i-1] - sum_pref[l-1] );
        }
        return ans;
    }
};

void solve(){
    int n; int a;
    cin >> n;
    Naszyjnik N(n);
    for(int i = 1; i <= n; i++){
        cin >> a;
        N.add_koral(i, a);
    }
    cout << N.solve() << "\n";
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}