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
#include <iostream>
#include <vector>

using namespace std;

struct seg {
    int N = 1;
    vector<int> v;

    seg(int n) {
        while (N < n) N <<= 1;
        v.resize(N * 2, 1e9);
    }

    void ins(int x, int a) {
        int i = x + N - 1;
        while (i) {
            v[i] = a;
            i >>= 1;
        }
    }

    int query(int i, int bg, int en, int x, int y) {
        if (x <= bg && en <= y) return v[i];
        
        int mid = (bg + en) >> 1;
        int res = 1e9;
        if (x <= mid) res = min(res, query(i * 2, bg, mid, x, y));
        if(y > mid) res = min(res, query(i * 2 + 1, mid + 1, en, x, y));
        return res;
    }

    void reset() {
        fill(v.begin(), v.end(), 1e9);
    }
};
int read() {
    int x = 0; int c = getchar_unlocked();
    while (c < '0' || c > '9') c = getchar_unlocked();
    while('0' <= c && c <='9') {
        x = x * 10 + (c - '0');
        c = getchar_unlocked();
    }
    return x;
}
int main() {
    int n;
    n = read();

    int mx = 0;
    int in;
    vector<int> tmp(n);
    for (int i = 0; i < n; ++i) {
        tmp[i] = read();
        if (tmp[i] >= mx) {
            mx = tmp[i];
            in = i;
        }
    }

    int it = n - 1;
    vector<int> v(n);
    for (int i = in; i >= 0; --i) {
        v[it] = tmp[i];
        --it;
    }   
    for (int i = n - 1; i > in; --i) {
        v[it] = tmp[i];
        --it;
    }

    int result = 0;
    vector<int> res(n);
    seg T(mx + 1);
    int last_reset = n - 2;
    for (int i = n - 1; i >= 0; --i) {
        if (v[i] == mx) {
            for (int j = last_reset; j > i; --j) {
                T.ins(v[j], 1e9);
            }
            last_reset = i;
        }
        int r = T.query(1, 1, T.N, v[i] + 1, mx + 1);
        if (r == 1e9) res[i] = 1;
        else res[i] = res[r] + 1;
        T.ins(v[i], i);
        result = max(result, res[i]);
    }

    printf("%d\n", result);
    
}