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

const int mxn = 2000005; 
int arr[mxn];
int len[mxn];
int uf[mxn]; 
int res, n; 

inline int f(int x, int y){
    if (arr[y] > arr[x] || (n<<1) <= y)
        return y;

    uf[y] =  f(x, uf[y]);
    return uf[y]; 
}

inline void u(int x){
    int i = f(x, x+1);
    uf[x] = i;  
    if ((n<<1) > i)
        len[x] = len[i] + 1;
    else
        len[x] = 1; 
}


int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cin >> n; 
    for (int i = 0; i < n; i++){
        cin >> arr[i];  
        arr[i+n] = arr[i]; 
    }

    for (int i = (n<<1)-1; i >= 0; i--)
        u(i);

    for (int i = 0; i < n; i++)
        res = max(res, len[i]);

    cout << res << '\n';
    return 0; 
}