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
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define loop(i,a,b) for (int (i) = (a); (i) < b; (i)++)
#define rloop(i,a,b) for (int (i) = (a); (i) >= b; (i)--)

vi t, lazy;

void push(int v)
{
    if (lazy[v])
    {
        t[v * 2] += lazy[v];
        t[v * 2 + 1] += lazy[v];
        lazy[v * 2] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
        lazy[v] = 0;
    }
}

void akt(int v, int obL, int obR, int l, int r, int w)
{
    if (obL > r || obR < l) return;
    if (obL >= l && obR <= r)
    {
        t[v] += w;
        lazy[v] += w;
        return;
    }
    push(v);
    int obM = (obL + obR) / 2;
    akt(v * 2, obL, obM, l, r, w);
    akt(v * 2 + 1, obM+1, obR, l, r, w);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);

    int n;

    cin >> n;

    int najbPot = (1 << ((int)ceil(log2(n))));

    t.resize(2*najbPot);
    lazy.resize(2*najbPot);

    vi w(2 * n + 1), wiekszyNaL(2*n+1);

    loop(i, 1, n+1)
    {
        cin >> w[i];
        w[i + n] = w[i];
    }

    stack<int> s;

    loop(i, 1, 2 * n + 1)
    {
        while (!s.empty() && w[s.top()] < w[i])
            s.pop();
        if (s.empty()) wiekszyNaL[i] = 0;
        else wiekszyNaL[i] = s.top();
        s.push(i);
    }

    loop(i, 1, 2 * n + 1)
    {
        int l = (max(max(1, (i - n + 1)), wiekszyNaL[i]+1)), r = min(n,i);
        akt(1, 1, n, l, r, 1);
    }
    
    cout << t[1];
    return 0;
}