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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> in_chain(n);
  int max_elem = -1;
  int max_poz;
  for(int i = 0; i < n; i++) {
    cin >> in_chain[i];
    if (in_chain[i] > max_elem) {
      max_elem = in_chain[i];
      max_poz = i;
    }
  }

  vector<int> chain(n);
  for(int i = 0; i < n; i++) {
    chain[i] = in_chain[(max_poz + i + 1) % n];
  }

  int result = 0;
  vector<int> DP(n);
  stack<int> s;
  for(int i = n-1; i >= 0; i--) {
    while(!s.empty() && chain[s.top()] <= chain[i]) {
      s.pop();
    }
    if(s.empty()) {
      DP[i] = 1;
    } else {
      DP[i] = DP[s.top()] + 1;
    }
    result = max(result, DP[i]);
    s.push(i);
  }

  cout << result << endl;


}