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
#include <cstdio>
#include <climits>
#include <stack>

int main(void)
{
	unsigned n;
	scanf("%u", &n);
	static int dupa[1000000];
	for (unsigned i = 0; i < n; i++)
		scanf("%u", &dupa[i]);
	static unsigned nge[1000000];
	std::stack<unsigned> stos;
	unsigned maxpos = UINT_MAX;
	for (int i = n - 1; i >= 0; i--) {
		while (!stos.empty() && dupa[stos.top()] <= dupa[i])
			stos.pop();
		if (stos.empty()) {
			nge[i] = i;
			maxpos = i;
		} else {
			nge[i] = stos.top();
		}
		stos.push(i);
	}
	unsigned pos = maxpos;
	unsigned maxres = 0;
	static unsigned res_at[1000001];
	do {
		unsigned res = res_at[nge[pos]] + 1;
		res_at[pos] = res;
		if (maxres < res)
			maxres = res;
		if (!pos)
			pos = n;
		pos--;
	} while (pos != maxpos);
	printf("%u\n", maxres);
	return 0;
}