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
76
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

#define MAX_N 2000005

#ifndef DEB_VAL
  #define DEB_VAL 0
#endif
#define DEB if(debug)

#define MP make_pair
#define PB push_back
#define FT first
#define SD second

int debug = DEB_VAL;

int n;
int tab[MAX_N];
int dl[MAX_N];
int ost[MAX_N];
int nxt[MAX_N];
int akt;
int h;

int main() {
  scanf("%d", &n);
  for(int i=0;i<n;i++){
    scanf("%d", tab+i);
    tab[i+n]=tab[i];
  }
  DEB for(int i=0;i<2*n;i++) {
    printf("%d ", tab[i]);
  }
  DEB printf("\n");
  nxt[2*n-1]=2*n-1;
  for(int i=2*n-2;i>=0;i--) {
    if(tab[i+1]>tab[i]) {
      nxt[i]=i+1;
    } else {
      akt=i+1;
      while(tab[akt]<=tab[i] && nxt[akt]!=akt) {
        akt=nxt[akt];
      }
      if(tab[akt]>tab[i]) {
        nxt[i]=akt;
      } else {
        nxt[i]=i;
      }
    }
  }
  DEB for(int i=0;i<2*n-1;i++) {
    printf("%d -> %d\n",i,nxt[i]);
  }
  for(int i=2*n-1;i>=0;i--) {
    if(nxt[i]==i) {
      dl[i]=1;
      ost[i]=i;
    } else {
      dl[i]=dl[nxt[i]]+1;
      ost[i]=ost[nxt[i]];
    }
  }
  DEB for(int i=0;i<2*n-1;i++) {
    if(ost[i]-i>n) { printf("BUG\n");}
    printf("%d -> %d ost: %d\n",i,dl[i],ost[i]);
  }
  int maks=0;
  for(int i=0;i<2*n-1;i++) {
    if(dl[i]>maks) maks=dl[i];
  }
  printf("%d",maks);
  return 0;
}