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
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
using ll = long long ;
using pii = pair <int,int> ;
using pll = pair<ll,ll> ;
using vi = vector <int> ; 
using vll = vector < ll > ;
using tiii = tuple<int,int,int> ; 
using ld = long double ; 

#define cYes {cout<<"YES\n";return;}
#define cNo {cout<<"NO\n";return;}
#define bra(x) "[" << (x) << "] "
#define ndl '\n' ;
#define all(x) (x).begin() , (x).end() 
#define sz(x) (int)(x).size() 
#define nd second 
#define st first
#define vvi vector<vector<int>> 

//#define DEBUG
#ifdef DEBUG 
#define dbg(x) cerr << #x << " = " << x << endl 
#else
#define dbg(x)
#endif

const int maxn = 1'000'007 , INFI = 1e9 + 77 ;
int arr[2*maxn] , N ;
pii mmerge( int l , int r ){
    int rr = (l<N)? N-1: r % N  ;
    int ll = (l<N)? r%N : l % N ;
    return { ll , rr } ;
}
int main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> N ;
    for(int i=1;i<=N;i++){
        cin >> arr[i] ;
        arr[i+N] = arr[i] ;
    }
    vector <pii> sta = { {INFI,0} } ;
    vi diff_arr(2*N+77,0) , diff_mem(2*N+77,0) ;
    for(int i=1;i<=2*N;i++){
        while(sta.back().st < arr[i] ) {
            sta.pop_back() ;
        }
        dbg(i) ;
        //cout << " lewy " << sta.back().nd << endl ;
        if(i>=N+1){
            int kand1 = ( max( i-N , sta.back().nd ) + 1 ) ;
            int kand2 = ( i ) ;
            diff_arr[(kand1-1) ] ++ ;
            diff_arr[kand2+1-1] -- ;
        }
        sta.push_back({arr[i],i}) ;
    }
    int bans = 0 , tans = 0 ;
    for(int i=0;i<2*N;i++){
        tans += diff_arr[i] ;
        diff_mem[i] = tans ;
        bans = max( bans , tans + ( (i-N<0)? 0 : diff_mem[i-N] ) ) ;
    }
    cout << bans << ndl ;
    return 0 ;
}