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
#include<iostream>
#include<vector>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int MAX_N = 1000000;

int A[2*MAX_N], R[2*MAX_N]; 

vector<int> P;

int res, n, n2, p;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	REP(i, n) { cin >> A[i]; A[i+n]=A[i]; }
	
	n2 = 2*n;
	
	int r0 = n2-1; R[r0] = -1;
	P.push_back(r0);

	FORD(i, n2-2, n) {
		while(P.size() > 0) {
			if (A[i] >= A[P[P.size()-1]]) {
				P.pop_back();				
			} else {
				break;
			}
		}
		P.push_back(i);
	}
	REP(i, n2) R[i] = 0;
	REP(j, P.size()) R[P[j]] = 1;
	
	int z = P.size(); res = z;
	
	// cerr << "z=" << z << endl;	
	// cerr << "z=" << z << " A[P[*]]=... "; REP(j, P.size()) cerr << A[P[j]] << " "; cerr << endl;
	
	FORD(i, n-1, 0) {
		int j = i+n;
		if (R[j]) z--;

		while(P.size() > 0) {
			if (A[i] >= A[P[P.size()-1]] && P[P.size()-1] < j) {
				R[P[P.size()-1]] = 0;
				P.pop_back();
				z--;
			} else {
				break;
			}
		}
		P.push_back(i);
		z++;

		// cerr << "z=" << z << " A[P[*]]=... "; REP(j, P.size()) cerr << A[P[j]] << " "; cerr << endl;

		if (z > res) res = z;
	}
			
	cout << res << endl;

	return 0;
}