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
#include <iostream>
using namespace std;
const int MAXN = 2000005;
const int MAXK = 18;
int T[MAXN];
int wieksze[MAXN][MAXK];
int N;
int last_wiekszy(int idx)
{
    int cnt = 0;
    int k = 17;
    while (k--)
    {
        while (wieksze[idx][k] != -1 && wieksze[idx][k] < idx + N)
        {
            idx += wieksze[idx][k] - idx;
            cnt += (1 << k);
        }
    }
    return cnt;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> T[i];
    for (int i = N; i < 2 * N; i++)
        T[i] = T[i % N];

    for (int i = 0; i < 2 * N; i++)
        for (int k = 0; k < MAXK; k++)
            wieksze[i][k] = -1;

    for (int i = 2 * N - 2; i >= 0; i--)
    {
        int idx = i + 1;
        while (idx != -1 && T[idx] <= T[i])
            idx = wieksze[idx][0];
        wieksze[i][0] = idx;
    }
    for (int k = 1; k < MAXK; k++)
    {
        for (int i = 0; i < 2 * N; i++)
        {
            if (wieksze[i][k - 1] == -1)
                wieksze[i][k] = -1;
            else
                wieksze[i][k] = wieksze[wieksze[i][k - 1]][k - 1];
        }
    }
    int result = 0;
    for (int i = 0; i < N; i++)
        result = max(result, last_wiekszy(i) + 1);
    cout << result << '\n';
}