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
#include <bits/stdc++.h>
int N,a[1000009],kk[1000009],st[1000009][21],ll[1000009];
inline int qma(int l,int r) {
	int dd=kk[r-l+1];
	return std::max(st[l][dd],st[r-(1<<dd)+1][dd]);
}
signed main(void) {
	scanf("%d",&N);
	for(int i=1;i<=N;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=2;i<=N;i++) {
		kk[i]=kk[i/2]+1;
	}
	for(int i=1;i<=N;i++) st[i][0]=a[i];
	for(int i=1;i<=kk[N];i++) {
		for(int j=1;j+(1<<i)-1<=N;j++) {
			st[j][i]=std::max(st[j][i-1],st[j+(1<<i-1)][i-1]);
		}
	}
	for(int i=1;i<=N;i++) {
		if(i==1||qma(1,i-1)<a[i]) {
			ll[1]++;
			ll[i+1]--;
			int l2=i+1,r2=N+1,mm;
			while(l2<r2) {
				mm=(l2+r2)/2;
				if(qma(mm,N)<a[i]) r2=mm;
				else l2=mm+1;
			}
			ll[l2]++;
			//jixu zuo hou mian de
		} else {
			int l=1,r=i,mm;
			while(l<r) {
				mm=(l+r)/2;
				if(qma(mm,i-1)<a[i]) r=mm;
				else l=mm+1;
			}
			ll[l]++;
			ll[i+1]--;
		}
	}
	int as=0;
	for(int i=1;i<=N;i++) {
		ll[i]+=ll[i-1];
		as=std::max(as,ll[i]);
	}
	printf("%d",as);
}