#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int, int> #define pb push_back #define ll long long #define TIME (1.0 * clock() / CLOCKS_PER_SEC) using namespace std; template <typename t1, typename t2> bool maximize(t1 &a, const t2 &b){if(a < b){a = b; return 1;} else return 0;}; template <typename t1, typename t2> bool minimize(t1 &a, const t2 &b){if(a > b){a = b; return 1;} else return 0;}; void load(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // if(fopen("test.inp", "r")){ // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // } } const int oo = 1e9 + 7; const ll OO = 1e18 + 7; const int maxn = 5e5 + 5; int n; int a[2 * maxn]; int pref[2 * maxn]; struct pp{ int val, id; }; deque<pp> dq; int k; int res = 0; void enter(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; a[i + n] = a[i]; } pref[0] = 0; for(int i = 1; i <= n * 2; i++){ pref[i] = pref[i - 1] + a[i]; } } int get_range(int l, int r){ return pref[r] - pref[l - 1]; } void add(int val, int id){ while(!dq.empty() && dq.back().val > val) dq.pop_back(); dq.push_back({val, id}); } void Try(){ k = (n + 1) / 2; for(int i = 1; i <= k; i++){ add(get_range(i, i + k - 1), i); } for(int i = k; i <= n + k - 1; i++){ while(dq.front().id <= i - k) dq.pop_front(); maximize(res, dq.front().val); add(get_range(i + 1, i + k), i); // cout << i << ' ' << res << ' ' << dq.front().id << ' ' << dq.back().id << ' ' << dq.back().val << '\n'; } cout << res; } signed main(){ load(); enter(); Try(); cerr << '\n' << "Time ran: " << TIME << "s\n"; }