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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;

const int MAXN = 2e6 + 7;

int a[MAXN];
int mx[4 * MAXN];
int ans[4 * MAXN];

int query_records(int v, int tl, int tr, int X){

	if(mx[v] <= X) return 0;
	
	if(tl == tr) return 1;

	int tm = (tl + tr) / 2;

	if(mx[2 * v] <= X){

		return query_records(2 * v + 1, tm + 1, tr, X);
	}
	else {

		return query_records(2 * v, tl, tm, X) + ans[v] - ans[2 * v];
	}
}

void build(int v, int tl, int tr){

	if(tl == tr){

		mx[v] = a[tl];
		ans[v] = 1;
		return;
	}

	int tm = (tl + tr) / 2;

	build(2 * v, tl, tm);
	build(2 * v + 1, tm + 1, tr);

	mx[v] = max(mx[2 * v], mx[2 * v + 1]);
	
	ans[v] = ans[2 * v] + query_records(2 * v + 1, tm + 1, tr, mx[2 * v]);
}

int query_range(int v, int tl, int tr, int l, int r, int &cur_max){

	if(l > r) return 0;

	if(l == tl && r == tr){

		int res = query_records(v, tl, tr, cur_max);
		cur_max = max(cur_max, mx[v]);
		
		return res;
	}

	int tm = (tl + tr) / 2;
	int res = 0;

	res += query_range(2 * v, tl, tm, l, min(r, tm), cur_max);
	res += query_range(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, cur_max);

	return res;
}

void solve(){

	int n;
	cin >> n;

	for(int i = 1; i <= n; i++){

		cin >> a[i];
		a[i + n] = a[i];
	}

	build(1, 1, 2 * n);

	int best = 0;

	for(int i = 1; i <= n; i++){

		int cur_max = -1;
		int act = query_range(1, 1, 2 * n, i, i + n - 1, cur_max);
		
		best = max(best, act);
	}

	cout << best << "\n";
}

bool multi = 0;

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int t = 1;
	if(multi) cin >> t;
	
	while(t--){

		solve();
	}

	return 0;
}