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

using namespace std;

int newIx(int i, int maxIx, int n) {
    int shift = n - maxIx;
    if (i < shift - 1) {
	return maxIx + i + 1;
    } else {
	return i - shift + 1;
    }
}

int main() {
    int n;
    scanf("%d\n", &n);

    int max = 0;
    int maxIx = -1;
    vector<int> pearls(n);
    for (int i = 0; i < n; i++) {
	scanf("%d", &pearls[i]);

	if (pearls[i] >= max) {
	    max = pearls[i];
	    maxIx = i;
	}
    }

    int curr = 0;
    int last = 0;
    stack<pair<int, int> > found;
    for (int i = 0; i < n; i++) {
	int ix = newIx(i, maxIx, n);

	if (pearls[ix] > last) {
	    curr++;

	    while (!found.empty() && found.top().first < curr) {
		found.pop();
	    }

	    if (!found.empty() && found.top().first == curr) {
	    }

	    while (!found.empty() && found.top().first >= curr) {
		if (found.top().first == curr) {
		    if (found.top().second >= pearls[ix]) {
			found.pop();
		    } else {
			found.pop();
			curr++;
		    }
		} else if (found.top().second <= pearls[ix]) {
		    curr = found.top().first + 1;
		    found.pop();
		}
	    }

	    last = pearls[ix];
	} else if (pearls[ix] < last) {
	    pair<int, int> currRes(curr, last);
	    found.push(currRes);

	    curr = 1;
	    last = pearls[ix];
	}

	printf("%d\n", curr);
    }

    return 0;
}