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
#include <bits/stdc++.h>

struct Queue {
	std::deque<std::pair<int, int>> q;
	Queue(int x, int i) : q{{x, i}} {}
	int f(int x, int i) {
		
		int ret;
		while (x > q.back().first) {
			q.pop_back();
		}
		ret = q.back().second;
		q.push_back({x, i});
		return ret;
	} 
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
	int n;
	std::cin >> n;

	std::vector<int> tab(n);
	std::vector<int> prev(n), begin(n, 0), end(n, 0);


	for (int i = 0; i < n; i++) {
		std::cin >> tab[i];
	}

	auto max_idx = std::ranges::distance(
		tab.begin(), 
		std::ranges::max_element(tab)
	);

	Queue q(tab[max_idx], max_idx);

	for (int i = 0, idx = (max_idx + 1) % n; i < n; i++, idx = (idx + 1) % n) {
 		prev[idx] = q.f(tab[idx], idx);
	}

	for (int i = 0; i < n; i++) {
		if ((prev[i] + 1) % n > i) {
			begin[0]++;
			end[i]++;

			begin[(prev[i] + 1) % n]++;
			end[n - 1]++;
		} else {
			begin[(prev[i] + 1) % n]++;
			end[i]++;
		}
	}

	long long sum = 0, answer = 0;

	for (int i = 0; i < n; i++) {
		sum += begin[i];
		answer = std::max(sum, answer);
		sum -= end[i];
	}

	std::cout << answer << "\n";
}