// O(n log n + n log s) optimized greedy simulation
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define rep(E, F) for (E = 0; E < (F); E++)
#define per(E, F) for (E = (F) - 1; E >= 0; E--)
#define PARENT(i) ((i - 1)/2)
#define LEFT(i)   ((i)*2 + 1)
#define RIGHT(i)  ((i)*2 + 2)
#define MAXN 5000001
typedef long long ll;
ll min(ll a, ll b) { if (a > b) return b; return a; }
ll max(ll a, ll b) { if (a < b) return b; return a; }
void swap(ll *a, ll *b) { ll s = *a; *a = *b; *b = s; }
ll get_int()
{
	ll r = 0, c = getchar(), s = 1;
	while (c != '-' && c < '0' || c > '9') c = getchar();
	while (c == '-') s *= -1, c = getchar();
	while (c >= '0' && c <= '9') r = r*10 + c - '0', c = getchar();
	return s*r;
}

typedef struct { ll x, y; } par;
par topar(ll x, ll y) { par r = {x, y}; return r; }
void par_swap(par *a, par *b) { par s = *a; *a = *b; *b = s; }
void fix_down(par *h, ll n, ll i)
{
	ll mx = i;
	if (RIGHT(i) < n && h[mx].x < h[RIGHT(i)].x) mx = RIGHT(i);
	if (LEFT(i) < n && h[mx].x < h[LEFT(i)].x) mx = LEFT(i);
	if (mx != i) par_swap(&h[i], &h[mx]), fix_down(h, n, mx);
}

void fix_up(par *h, ll n, ll i)
{
	if (i == 0) return;
	else if (h[i].x > h[PARENT(i)].x) par_swap(&h[i], &h[PARENT(i)]), fix_up(h, n, PARENT(i));
}

void pop(par *h, ll n) { h[0] = h[n - 1], fix_down(h, n - 1, 0); }
void push(par *h, ll n, par x) { h[n] = x, fix_up(h, n + 1, n); }
par peek(par *h) { return h[0]; }

par h[2*MAXN];
void nge(ll* a, ll* b, ll n)
{
	ll c = 0, i;
	for (i = 0; i < n; i++)
	{
		while (c > 0 && -2*peek(h).x < a[i]) b[peek(h).y] = i, pop(h, c--);
		push(h, c++, topar(-a[i], i));
	}
	while (c > 0) b[peek(h).y] = -1, pop(h, c--);
}

ll rsum(ll *s, ll n, ll x, ll y)
{ // [x, y[. sums to the right.
	if (y == -1) return 0; // its done anyway
	if (x == y) return 0;
	if (x > y) return rsum(s, n, 0, y) + rsum(s, n, x, n);
	assert(y != 0);
	return s[y - 1] - (x == 0 ? 0 : s[x - 1]);
}

ll lsum(ll *s, ll n, ll x, ll y)
{
	if (y == -1) return 0; // its done anyway
	return s[n - 1] - rsum(s, n, (x + 1)%n, (y + 1)%n);
}

ll a[2*MAXN], l[2*MAXN], r[2*MAXN], s[MAXN];
int main()
{
	srand(1010);
	ll i, n = get_int(), t, x, y, z, w = (1LL << 60), mx = 0;
	rep(i, n) a[i + n] = a[i] = get_int();
	rep(i, n) mx = max(mx, a[i]);
	nge(a, r, 2*n);
	rep(i, n) swap(&a[i], &a[2*n - 1 - i]);
	nge(a, l, 2*n);
	rep(i, n) swap(&a[i], &a[2*n - 1 - i]);
	rep(i, n) swap(&l[i], &l[2*n - 1 - i]);
	rep(i, n) l[i] = l[i + n]%n, r[i] %= n;
	rep(i, n) if (l[i] != -1) l[i] = n - 1 - l[i];
	rep(i, n) s[i] = a[i] + (i != 0 ? s[i - 1] : 0);
	rep(i, n)
	{
		t = (l[i] == -1 ? 2*a[i] : 0), z = a[i], x = l[i], y = r[i];
		t += lsum(s, n, i, x) + rsum(s, n, i, y);
		while (t < mx && z < w)
		{
			if (a[x] <= a[y])
			{
				if (a[x] > t) z += a[x] - t, t = a[x];
				t += l[x] == -1 ? a[x] : lsum(s, n, x, l[x]);
				x = l[x];
			}
			else
			{
				if (a[y] > t) z += a[y] - t, t = a[y];
				t += r[y] == -1 ? a[y] : rsum(s, n, y, r[y]);
				y = r[y];
			}
		}
		w = min(w, z);
	}
	printf("%lld\n", w);
	return 0;
}