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
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
constexpr int MAXN = 1e6+11;
int A[2*MAXN];
int seq[MAXN];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n{};
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> A[i];
    A[n+i] = A[i];
  }
  int l{1};
  int last{0};
  A[0] = 1e6+12;
  stack<int> stos;
  vector<pii> up;
  up.push_back({A[1], 1});
  for(int i = 2; i <= n; ++i) {
    if(A[i] > up.back().first) up.push_back({A[i], i});
  }
  up.push_back({1e6+2, 1e6+2});
  for(int i = n; i >= 1; --i) {
    while(stos.size() && stos.top() <= A[i]) stos.pop();
    stos.push(A[i]);
    seq[i] = stos.size();
  }
  int maks{};
  int iter{};
  int ans{};
  for(int i = n; i >= 1; --i) {
    maks = max(maks, A[i]);
    while(iter < up.size() && maks >= up[iter].first) iter++;
    int cur = seq[i];
    auto [val, id] = up[iter];
    if(id < i) cur += up.size()-iter-1;
    ans = max(ans, cur);
  }
  cout << ans << '\n';
}