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
#include "bits/stdc++.h"
using namespace std;

int const N = 1e6+6;
int n, a[N], b[N], mx, mx_id, dp[N], ans;
vector <int> v;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        if(a[i] > mx){
            mx = a[i];
            mx_id = i;
        }
    } 
    int curr1 = (mx_id+1)%n, curr2 = 0;
    for(;curr2 < n;){
        b[curr2++] = a[curr1++];
        if(curr1 >= n) curr1 = 0;
    }
    for(int i = n-1; ~i; --i){
        while(v.size() && b[v.back()] <= b[i]) v.pop_back();
        dp[i] = (v.empty() ? 0 : dp[v.back()]) + 1;
        v.push_back(i);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}