#include <bits/stdc++.h>
#define ll long long
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define all(x) begin(x), end(x)
#define endl '\n'
using namespace std;
const int MAX = 1e6 + 5; // Tăng lên gấp đôi vì mình sẽ nhân đôi mảng
int n;
int a[MAX]; // Input ban đầu
ll sum[MAX]; // Mảng tổng cửa sổ trượt (Prefix sum cũng được)
void solve() {
// 1. Nhân đôi mảng để xử lý vòng tròn dễ hơn
// a[0]...a[n-1] -> a[0]...a[2n-1]
for(int i = 0; i < n; ++i) a[i + n] = a[i];
// Độ dài cửa sổ mà Hacker tác động (thường là N/2)
int window = (n + 1) / 2;
// 2. Tính tổng của mọi cửa sổ độ dài `window`
// s là biến cộng dồn tạm thời
ll s = 0;
// Tính cửa sổ đầu tiên [0...window-1]
for(int i = 0; i < window; ++i) s += a[i];
sum[0] = s;
// Tính các cửa sổ tiếp theo bằng Sliding Window O(N)
// sum[i] là tổng của đoạn bắt đầu từ i: a[i]...a[i+window-1]
for(int i = 1; i < 2 * n; ++i) {
s -= a[i - 1]; // Bỏ phần tử cũ
if (i + window - 1 < 2 * n) // Kiểm tra biên
s += a[i + window - 1]; // Thêm phần tử mới
sum[i] = s;
}
// 3. Dùng Deque tìm Min/Max tùy theo đề bài
// Giả sử logic của bạn là: Tìm max của (min các cửa sổ sum trong phạm vi nào đó)
// Code dưới đây giữ nguyên logic logic "Max of Mins" của bạn
deque<int> q; // Lưu chỉ số
vector<ll> b(n * 2, -1e18); // Lưu kết quả
// Cần xác định rõ phạm vi sliding window của bước 2
// Ví dụ: Với mỗi vị trí i, xét các đoạn sum trong khoảng [i, i + k...]
// Ở đây mình minh họa khung sườn, bạn lắp logic phạm vi vào nhé
/* LƯU Ý: Đoạn logic dưới này phụ thuộc vào việc Hacker xóa đoạn nào.
Nếu Hacker xóa đoạn độ dài L bắt đầu tại j sao cho i thuộc đoạn đó?
Hay Hacker xóa đoạn bất kỳ?
Thường bài này là:
Total_Sum - (Max sum đoạn con độ dài L).
Nhưng nếu code bạn dùng queue để tìm min/max cục bộ thì áp dụng vào đây.
*/
// Demo Logic Deque chuẩn:
int query_range = n - window + 1; // Ví dụ độ dài phạm vi query
for (int i = 0; i < n * 2; ++i) {
// 1. Pop phần tử quá hạn ra khỏi đầu hàng đợi
if (!q.empty() && q.front() < i - query_range + 1) q.pop_front();
// 2. Duy trì tính đơn điệu (Giả sử tìm MIN thì pop các thằng LỚN hơn)
while (!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
// 3. Push hiện tại vào
q.push_back(i);
// 4. Lấy kết quả (Min trong cửa sổ hiện tại)
if (i >= query_range - 1) {
// sum[q.front()] chính là min sum trong phạm vi
// logic của bạn ở đây...
}
}
}
void input() {
cin >> n;
REP(i, n) cin >> a[i];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
// openFile("hacker"); // Nếu nộp bài cần file
input();
solve();
}
