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
// #define DEBUG
#include <iostream>
#include <map>
#ifdef DEBUG
#include <iomanip>
#endif

const int MAX = 1000005;
const int MAXK = 20;

int A[MAX * 2];
int N[MAX * 2][MAXK];

int solve(int i, int n, int k) {
  if (i >= n) return 0;
  if (k < 0) return 0;
  int ni = N[i][k];
  if (ni < n)
    return solve(ni, n, k - 1) + (1 << k);
  else
    return solve(i, n, k - 1);
}

int main() {
  std::ios_base::sync_with_stdio(0);
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) std::cin >> A[i];
  for (int i = 0; i < n; ++i) A[i + n] = A[i];
  std::map<int, int> M;
  A[2*n] = MAX;
  M[MAX] = 2 * n;
  for (int i = 0; i < MAXK; ++i) N[2*n][i] = 2*n;
  for (int i = 2 * n - 1; i >= 0; --i) {
    while (M.begin()->first <= A[i]) M.erase(M.begin());
    N[i][0] = M.begin()->second;
    for (int k = 1; k < MAXK; ++k) N[i][k] = N[N[i][k - 1]][k - 1];
    M[A[i]] = i;
  }
#ifdef DEBUG
  for (int i = 0; i <= 2 * n; ++i) {
    std::clog << std::setw(4) << i;
  }
  std::clog << std::endl;
  for (int i = 0; i <= 2 * n; ++i) {
    std::clog << std::setw(4) << (A[i] < MAX ? A[i] : -1);
  }
  std::clog << std::endl;
  for (int i = 0; i <= 2 * n; ++i) {
    std::clog << std::setw(4) << N[i][0];
  }
  std::clog << std::endl;
#endif
  int best = 0;
  for (int i = 0; i < n; ++i) {
    best = std::max(best, solve(i, i + n, MAXK - 1)+1);
  }

  std::cout << best << std::endl;

  return 0;
}