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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;
#define PB push_back
#define LL long long
#define int LL
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define VI vector<int>
#define PII pair<int,int>
#define LD long double

template<class C> void mini(C& a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C& a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream &os, vector<T> V){
  os<<"[";for(auto vv:V)os<<vv<<",";return os<<"]";
} 

template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}


#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

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

    int n;
    cin >> n;
    VI a(n);
    REP(i, n) cin >> a[i];

    int m = 2 * n;
    VI b(m);
    REP(i, m) b[i] = a[i % n];

    VI ng(m, m);
    VI stk;
    REP(i, m) {
        while (SZ(stk) && b[stk.back()] < b[i]) {
            ng[stk.back()] = i;
            stk.pop_back();
        }
        stk.PB(i);
    }


    int LOG = 1;
    while ((1 << LOG) <= m) LOG++;

    vector<VI> jump(LOG, VI(m, m));
    jump[0] = ng;
    FOR(k, 1, LOG - 1) {
        REP(i, m) {
            if (jump[k - 1][i] < m)
                jump[k][i] = jump[k - 1][jump[k - 1][i]];
        }
    }

    int ans = 0;
    REP(s, n) {
        int count = 1;
        int pos = s;
        int limit = s + n;
        FORD(k, LOG - 1, 0) {
            if (jump[k][pos] < limit) {
                count += (1 << k);
                pos = jump[k][pos];
            }
        }
        maxi(ans, count);
    }

    cout << ans << "\n";
    return 0;
}