#include <bits/stdc++.h>
#define N 1000011
#define ll long long
using namespace std;
int n,a[N];
vector<int> va[N],vv;
const int A=1e6;
ll dp[N],ndp[N],f[N],suml[N],sumle[N];
int prv[N],nxt[N],nxtle[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",a+i),a[n+i]=a[i],va[a[i]].push_back(i);
	int lst=A+1;
	memset(dp,0x3f,sizeof(dp));
	for(int x=A;x;--x)if(!va[x].empty())
	{//printf("===============================x:%d\n",x);
		for(int i=1;i<=2*n;++i)suml[i]=suml[i-1]+(a[i]<x)*a[i],sumle[i]=sumle[i-1]+(a[i]<=x)*a[i];
		for(int i=1;i<=2*n;++i)f[i]=1e18;
		nxtle[2*n+1]=2*n+1;
		for(int i=2*n+1;i;--i)if(a[i]<=x)nxtle[i]=i;else nxtle[i]=nxtle[i+1];
		if(lst<=A)
		{
			for(int i:va[lst])
			{
				int u=nxtle[i];
				if(u>n)u-=n;
				f[u]=f[u+n]=min(f[u],dp[i]);
			}
		}
		else f[1]=f[n+1]=0;
		// printf("f:");for(int i=1;i<=2*n;++i)printf("%lld ",f[i]);putchar(10);
		for(int i=1;i<=2*n;++i)if(a[i]==x)prv[i]=i;else prv[i]=prv[i-1];
		for(int i=2*n;i;--i)if(a[i]==x)nxt[i]=i;else nxt[i]=nxt[i+1];
		for(int i=n+1;i<=2*n;++i)if(a[i]==x)
		{
			int u=i,v=prv[i-1];
			if(v+n==u)continue;
			// printf("typ1 u:%d v:%d\n",u,v);
			for(int S=v;S<=u;++S)dp[u-n]=min(dp[u-n],suml[u]-suml[v-1]+sumle[S-1]-sumle[v-1]+f[S]);
			// printf("new dp[%lld]:%lld\n",u-n,dp[u-n]);
		}
		// printf("dp:");for(int i=1;i<=n;++i)printf("%lld ",dp[i]);putchar(10);
		for(int i=1;i<=n;++i)if(a[i]==x)
		{
			int u=i,v=nxt[i+1];
			if(v-n==u)continue;
			for(int S=u;S<=v;++S)dp[u]=min(dp[u],sumle[S-1]-sumle[u-1]+2*(suml[v]-suml[S-1])+f[S]);
		}
		for(int u=n+1;u<=2*n;++u)if(a[u]==x)
		{
			int v=nxt[u-n+1];//printf("typ3 u:%d v:%d\n",u,v);
			for(int S=u-n+1;S<=v;++S)dp[u-n]=min(dp[u-n],suml[u]-suml[S-1]+f[S]);
			// printf("new dp[%lld]:%lld\n",u-n,dp[u-n]);
		}
		for(int u=1;u<=n;++u)if(a[u]==x)
		{
			int v=prv[u+n-1];
			for(int S=v;S<u+n;++S)dp[u]=min(dp[u],sumle[S-1]-sumle[u-1]+f[S]);
		}
		lst=x;
		// printf("dp:");for(int i=1;i<=n;++i)printf("%lld ",dp[i]);putchar(10);
	}
	ll ans=1e18;
	for(int i:va[lst])ans=min(ans,dp[i]);
	printf("%lld\n",ans);
	fclose(stdin);fclose(stdout);return 0;
}