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
#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int MAXA=1e6;
const int baza=2097152;

int tree[baza*2+3];
vector<int> a1,a2;
int n;

int query(int l, int r, int a, int v, int l2, int r2)
{
    if(l>r2 || r<l2 || tree[v]<=a) return -1;
    if(l2==r2) return l2;

    int mid=(l2+r2)/2;

    int lewy=query(l,r,a,v*2,l2,mid);
    if(lewy!=-1) return lewy;
    return query(l, r, a, v*2+1, mid+1, r2);

}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n;

    for(int i=0; i<n; i++)
    {
        int akt; cin>>akt; a1.push_back(akt);
    }
    for(int i=0; i<2*n; i++)    a2.push_back(a1[i%n]);

    for(int i=0; i<a2.size(); i++) tree[baza+i]=a2[i];
    for(int i=baza-1; i>=1; i--) tree[i]=max(tree[i*2],tree[i*2+1]);

    vector<int> nast(n, -1);
    for(int i=0; i<n; i++)
    {
        int akt=query(i+1, i+n-1, a1[i],1,0,baza-1);
        if(akt!=-1) nast[i]=akt%n;
    }

    vector<int> dp(n+1,-1);
    int ans=1;

    for(int i=0; i<n; i++)
    {
        if(dp[i]!=-1)   {ans=max(ans,dp[i]); continue;}

        int j=i;
        stack<int> stos;
        while(j!=-1 && dp[j]==-1)
        {
            stos.push(j);
            j=nast[j];
        }

        int akt=0;
        if(j!=-1) akt=dp[j];

        while(!stos.empty())
        {
            int x=stos.top();
            stos.pop();
            akt++;
            dp[x]=akt;
            ans=max(ans,dp[x]);
        }
    }

    cout<<ans<<'\n';


}