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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

#define int long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;


void test() {
    debug("TC______________________");
    int n; cin>>n;
    vector <int> v(2*n+1);
    vector <int> spec(2*n+1);
    int mx = 0, cur = 0, last = 0;

    for (int i=0; i<n; ++i) {
        cin>>v[i];
        v[i+n] = v[i];
        if (v[i] > mx) {
            spec[i] = true;
            mx = v[i];
            cur++;
            last = max(last, i);
        }
    }


    stack <pii> st;
    st.push({1e9+7, 2*n});
    vector <int> next(2*n+1);
    for (int i=2*n; i>=0; --i) {
        while (st.top().fi < v[i]) {
            st.pop();
        }
        next[i] = st.top().se;
        st.push({v[i], i});
    }

    debug(next);

    int res = cur;
    debug(spec, cur);
    int opc = 0;
    for (int i=0; i<n; ++i) {
        if (spec[i]) {
            spec[i] = 0;
            cur--;
            int j = i+1; int mxt = 0;
            while (j < i + n && !spec[j]) {
                opc++;
                if (v[j] > mxt) {
                    if (spec[j] == 0) cur++;
                    spec[j] = 1;
                    mxt = v[j];
                    last = max(last, j);
                }   
                j = next[j];
            }
        }
        if (v[i] > v[last]) {
            if (spec[i+n] == 0) cur++;
            spec[i+n] = 1;
            last = max(last, i+n);
        }
        res = max(res, cur);
        debug(i, cur);
        debug(spec);
    }
    debug(opc);
    cout<<res<<'\n';
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t = 1; 
  while (t--) {
    test();
  }
}