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
#include <iostream>
#include <queue>
using namespace std;
int n;
int const max_N = 1000002;
int koralik[2 * max_N];
int next_koralik[21][2 * max_N];

int find_steps_before(int i, int k) {
	int jump_len = 0;
	int cur_step = 20;
	while (cur_step >= 0) {
		if (next_koralik[cur_step][i] < k) {
			jump_len += (1 << cur_step);
			i = next_koralik[cur_step][i];
		}
		cur_step--;
	}
	return jump_len;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		koralik[i] = k;
		koralik[i + n] = k;
	}
	koralik[2 * n] = max_N;
	auto last = priority_queue<pair<int, int>, std::vector<pair<int, int>>, std::greater<pair<int, int>>>();
	last.push({koralik[0], 0});
	for (int i = 1; i < 2 * n+1; i++) {
		while (!last.empty() && koralik[i] > last.top().first) {
			pair<int, int> tmp = last.top();
			next_koralik[0][tmp.second] = i;
			last.pop();
		}
		last.push({ koralik[i], i });
	}
	next_koralik[0][2 * n] = 2 * n;
	for (int step = 1; step < 21; step++) {
		for (int j = 0; j < 2 * n + 1; j++) {
			next_koralik[step][j] = next_koralik[step - 1][next_koralik[step - 1][j]];
		}
	}
	int answer = 0;
	for (int i = 0; i <  n; i++) {
		answer = max(answer, find_steps_before(i, i + n));
	}
	cout << answer + 1;
}