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
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

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

   int n; cin >> n;

   vector<int> nums(2*n + 1);
   for (int i = 0; i < n; i++) cin >> nums[i];
   for (int i = n; i < 2*n; i++) nums[i] = nums[i - n];
   nums[2*n] = 1e6 + 1;

   vector<int> h(2*n + 1);
   stack<int> s;
   s.push(2*n);
   for (int i = 2*n - 1; i >= 0; i--) {
      int a = nums[i];
      while (a >= nums[s.top()]) s.pop();
      // cerr << i << ' ' << s.top() << endl;
      h[i] = h[s.top()] + 1;
      s.push(i);
   }

   int maxi = 0;
   for (int i = 0; i < n; i++) {
      maxi = max(maxi, h[i]);
   }
   cout << maxi << endl;

   return 0;
}