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
#include "bits/stdc++.h"
using namespace std;

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

    int n;
    cin >> n;

    vector<int> pearls;
    pearls.resize(2*n);

    for(int i=0; i<n; i++) {
        cin >> pearls[i];
        pearls[n+i] = pearls[i];
    }

    vector<int> previous_higher;
    previous_higher.resize(n*2);
    vector<int> previous;

    for(int i=0; i<n*2; i++) {
        if(previous.empty()) {
            previous_higher[i] = -1;
        } else {
            while(!previous.empty() && pearls[i] > pearls[previous.back()]) {
                previous.pop_back();
            }

            if(previous.empty()) {
                previous_higher[i] = -1;
            } else {
                previous_higher[i] = previous.back();
            }
        }
        previous.push_back(i);
    }

    vector<int> count;
    count.assign(n, 0);

    int from, to;

    for(int i=0; i<n*2; i++) {
        from = previous_higher[i] + 1;
        to = i;
        if(from < i-n+1 ) {
            from = i-n+1;
        }
        if(to > n-1) {
            to = n-1;
        }
        if(from<=to) {
            count[from]++;
            count[to+1]--;
        }
    }

    int result = 0;
    int start_from = 0;

    for(int i=0; i<n; i++) {
        start_from += count[i];
        if(start_from > result) {
            result = start_from;
        }
    }

    cout<<result<<"\n";

    return 0;

}