#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";
}
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"; } |
English