#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;

// Same as ragnar.cpp, but when expanding the range, directly jump to the next
// larger value, instead of only expanding the range by 1.

// All-nearest-larger-values:
// For each position, find the first position on the left and right with a larger value.
auto ansv(vector<long long>& a) {
	vector<int> l(a.size(), -1), r(a.size(), -1);
	for(int i = 1; i < a.size(); ++i) {
		l[i] = i - 1;
		while(l[i] >= 0 && a[i] > a[l[i]]) l[i] = l[l[i]];
	}
	for(int i = a.size() - 2; i >= 0; --i) {
		r[i] = i + 1;
		while(r[i] >= 0 && a[i] > a[r[i]]) r[i] = r[r[i]];
	}
	return pair(l, r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<long long> v(n), V;
	long long ans = 0;
	for(auto& x : v) {
		cin >> x;
		ans = max(x, ans);
	}
	v.reserve(4 * n);
	for(auto x : v) v.push_back(x);
	for(auto x : v) v.push_back(x);

	// prefix sums
	exclusive_scan(begin(v), end(v), back_inserter(V), 0ll);

	auto [L, R] = ansv(v);

	for(int i = n; i < 2 * n; ++i) {
		if(v[i - 1] < v[i] or v[i] > v[i + 1]) continue;
		int l = i, r = i;
		long long s = 0, t = 0;
		while(s < ans and r - l < n) {
			if(v[l - 1] < v[r]) {
				auto e = --l;
				if(v[e] > t) s += v[e] - t, t = v[e];
				l = max(L[l] + 1, r - n);
				t += V[e + 1] - V[l];
			} else {
				auto e = r++;
				if(v[e] > t) s += v[e] - t, t = v[e];
				r = min(R[r - 1], l + n);
				t += V[r] - V[e];
			}
		}
		ans = min(ans, s);
	}
	cout << ans << endl;
}