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
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    vector<int> b(2*n+1);
    for(int i=1;i<=n;i++){
        b[i] = a[i];
        b[i+n] = a[i];
    }
    vector<int> s;
    vector<int> r(2*n+1,0);
    for(int i=2*n; i>0; i--){
        while(!s.empty() and b[s.back()] < b[i]){
            s.pop_back();
        }
        if(s.empty()){
            r[i] = 2*n+1;
        }
        else{
            r[i] = s.back();
        }
        s.push_back(i);
    }
    vector<int> s2;
    vector<int> l(2*n+1,0);
    for(int i=1;i<=2*n;i++){
        while(!s2.empty() && b[s2.back()] < b[i]){
            s2.pop_back();
        }
        if(s2.empty()){
            l[i] = 0;
        }
        else{
            l[i] = s2.back();
        }
        s2.push_back(i);
    }
    vector<int> cnt(n+2,0);
    for(int i=1;i<=2*n;i++){
        int lewy = max(l[i]+1, i-n+1);
        int prawy = min(i, n);

        lewy = max(lewy, 1);
        prawy = min(prawy, n);

        if(lewy <= prawy){
            cnt[lewy] += 1;
            cnt[prawy+1] -= 1;
        }
    }
    int ak = 0;
    int w = 0;
    for(int i=1;i<=n;i++){
        ak += cnt[i];
        w = max(w, ak);
    }

    cout << w;
}