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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ssize(x) int((x).size())

int main() {
    int n; scanf("%d", &n);
    vector <int> a(n);
    for(int &x : a) scanf("%d", &x);

    vector <int> seq_suf, seq_pref;

    for(int i = 0; i < n; ++i)
        if(seq_pref.empty() || a[i] > a[seq_pref.back()]) seq_pref.pb(i);

    int ans = ssize(seq_pref), m = 0;

    for(int i = n - 1, l = 0; i; --i) {
        m = max(m, a[i]);

        while(!seq_suf.empty() && a[i] >= seq_suf.back()) seq_suf.pop_back();
        seq_suf.pb(a[i]);

        if(!seq_pref.empty() && seq_pref.back() == i) seq_pref.pop_back();

        while(l < ssize(seq_pref) && a[seq_pref[l]] <= m) ++l;

        ans = max(ans, ssize(seq_suf) + max(ssize(seq_pref) - l, 0));
    }

    printf("%d\n", ans);
    return 0;
}