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;

vector<int>v;
vector<pair<int,int>>ilenaprawo;
vector<pair<int,int>>ilezaczynajacodlewej;
stack<int>s;

int policz(int idx){
    int res=0;

    res+=ilenaprawo[idx].first;
    int odktorej=ilenaprawo[idx].second+1;

    if(idx==0){
        return res;
    }

    res+=ilezaczynajacodlewej[idx-1].second;

    auto it=lower_bound(
        ilezaczynajacodlewej.begin(),
        ilezaczynajacodlewej.begin()+idx,
        make_pair(odktorej,-1)
    );

    int gdzie=it-ilezaczynajacodlewej.begin();

    if(gdzie<idx){
        res-=ilezaczynajacodlewej[gdzie].second;
    }

    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;

    v.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    for(int i=n-1;i>=0;i--){
        while(!s.empty()&&s.top()<v[i]){
            s.pop();
        }
        s.push(v[i]);
        ilenaprawo.push_back({(int)s.size(),v[i]});
    }
    reverse(ilenaprawo.begin(),ilenaprawo.end());

    int rekord=-1;
    int licz=0;

    for(int i=0;i<n;i++){
        if(v[i]>rekord){
            licz++;
            rekord=v[i];
        }
        ilezaczynajacodlewej.push_back({rekord,licz});
    }

    int wynik=0;

    for(int i=0;i<n;i++){
        wynik=max(wynik,policz(i));
    }

    cout<<wynik;
}