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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(__typeof(b) i = a; i < b; ++i)
#define FORev(i,a,b) for(__typeof(a) i = a; i >= b; --i)
#define c(x) cin >> x

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n; c(n);
    vector<ll> a(2*n);
    FOR(i,0,n){
        c(a[i]);
        a[i+n] = a[i];
    }

    vector<ll> maksi(2*n,-1);
    stack<ll> st;
    FOR(i,0,2*n){
        while (!st.empty() && a[st.top()] < a[i])
            st.pop();
        if (!st.empty())
            maksi[i] = st.top();
        st.push(i);
    }
    vector<ll> segs(n+1, 0);
    FOR(i,0,2*n){
        ll l = max(0LL, max(maksi[i]+1,i-n+1));
        ll r = min(i,n-1);
        if (l <= r){
            segs[l]++;
            if (r+1 < n) segs[r+1]--;
        }
    }

    ll res = 0,cnt = 0;
    FOR(i,0,n){
        cnt += segs[i];
        res = max(res,cnt);
    }

    cout << res << "\n";
}