#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 500005;
int a[N],n;
ll ans = 0,dp[N],pref[N],suff[N];
void comp(int x) {
memset(dp,0,n + 5);
memset(pref,0,n + 5);
memset(suff,0,n + 5);
for (int i = 1; i <= n;i++) pref[i] = pref[i - 1] + a[i];
for (int i = n; i > 0;i--) suff[i] = suff[i + 1] + a[i];
for (int i = x + 1; i <= n;i++) {
int r = (i - x) / 2,l = (x + (n - i)) / 2;
// cerr << x << " " << i << " " << l << " " << r << "\n";
dp[i] = a[x];
if (l % 2 && r % 2) {
if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
else dp[i] += (pref[x - 1] - pref[x - l - 1]);
if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
else dp[i] += pref[x + r] - pref[x];
int p1 = (x - l + n) % n, p2 = (x + r) % n;
if (p1 == 0) p1 = n;
if (p2 == 0) p2 = n;
dp[i] -= min(a[p1],a[p2]);
}else {
int p = 0, p1 = n;
if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
else dp[i] += (pref[x - 1] - pref[x - l - 1]);
if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
else dp[i] += pref[x + r] - pref[x];
}
}
for (int i = x - 1; i >= 1;i--) {
int l = (x - i) / 2,r = ((n - x) + i) / 2;
//cerr << x << " " << i << " " << l << " " << r << "\n";
dp[i] = a[x];
if (l % 2 && r % 2) {
if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
else dp[i] += (pref[x - 1] - pref[x - l - 1]);
if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
else dp[i] += pref[x + r] - pref[x];
int p1 = (x - l + n) % n, p2 = (x + r) % n;
if (p1 == 0) p1 = n;
if (p2 == 0) p2 = n;
dp[i] -= min(a[p1],a[p2]);
}else {
int p = 0, p1 = n;
if (l >= x) dp[i] += pref[x - 1] + suff[n - (l - x)];
else dp[i] += (pref[x - 1] - pref[x - l - 1]);
if (r > n - x) dp[i] += pref[n] - pref[x] + pref[(r - (n - x))];
else dp[i] += pref[x + r] - pref[x];
}
}
}
void task1() {
for (int i = 1; i <= n;i++) {
comp(i);
ll cur = 1e18;
// for (int j = 1; j <= n;j++) cerr << dp[j] << " ";
// cerr << " ---- \n";
for (int j = 1; j <= n;j++) if (i!=j) cur = min(cur,dp[j]);
ans = max(ans,cur);
}
cout << ans;
}
void task2() {
comp(1);
// for (int i = 1; i <= n;i++) cerr << dp[i] << " ";
// cerr << "\n";
for (int i = 1; i <= n;i++) ans = min(ans,dp[i]);
cout << ans;
}
void solve() {
cin >> n;
for (int i = 1; i <= n;i++) cin >> a[i];
//task2();
if (n <= 5000) {
task1();
}else {
task2();
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
cout << "\n";
}
return 0;
}
