/*
考虑直接使用 kruskal 算法，对 $a$ 进行排序，这要求我们对 $k=u+(k-u)$ 的所有边 $(u,v)$ 尽量连边。那么我们需要支持插入该边权所有边以及查询这类边会有多少条在边在 MST 中。然后可以考虑经典套路，对于每一次拓展二分找到对于当前 $k$ 最小的一对不在同一个连通块中的边。那么就需要判定 $V=[l,r]\cup[k-r,k-l]$ 是否满足每个对应的边都不是同一个连通块。我们考虑对于同一种连通块的颜色，给这个点赋上这个颜色对应的权值，这个权值是你给出的两两不同的任意实数，可以用 $[0,2^{64}-1]$ 中随机正整数代替，那么我们要求找出首个不是同个连通块的，也就是说两者权值不同。我们要求极长保留的，要求 $i,k-i$ 的颜色相同，这相当于判定是否构成回文串。线段树维护一下正反串的哈希值，然后对于每次加边即合并连通块，使用启发式合并修改小集合中每个点的颜色为大集合的颜色。时间复杂度 $\mathcal O(n\log^2n)$。

懒得写了。

*/


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N=4e5+3;
ll n,ans,a[N],id[N],f[N],leaf[N];
vector<int>ve[N]; 
ull bas=998244853,pw[N],col[N];
mt19937 rd(654321);
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
struct Info{ull v;int len;};
Info operator +(Info A,Info B){return {A.v*pw[B.len]+B.v,A.len+B.len};}
#define mi ((l+r)>>1)
struct SGT
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define lson ls,l,mi
	#define rson rs,mi+1,r
	Info tr[(1<<19)+3];
	void Up(int p){tr[p]=tr[ls]+tr[rs];}
	void Build(int op,int p=1,int l=1,int r=n)
	{
		if(l==r){tr[p]={!op?col[l]:col[n-l+1],1};leaf[l]=p;return;}
		Build(op,lson);Build(op,rson);Up(p);
	}
	void Mdf(int p,ull v)
	{
		p=leaf[p];tr[p]={v,1};
		while(p>1)Up(p>>=1);
	}
	Info Ask(int L,int R,int p=1,int l=1,int r=n)
	{
		if(L<=l&&r<=R)return tr[p];
		if(R<=mi)return Ask(L,R,lson);
		if(L>mi)return Ask(L,R,rson);
		return Ask(L,R,lson)+Ask(L,R,rson); 
	}
}T0,T1;
bool Chk(int l,int r,int len){return T0.Ask(l,l+len-1).v==T1.Ask(n-r+1,n-r+len).v;}
void Mer(int x,int y)
{
	x=F(x);y=F(y);
	if(ve[x].size()<ve[y].size())swap(x,y);
	for(int v:ve[y])ve[x].push_back(v),col[v]=col[x],T0.Mdf(v,col[v]),T1.Mdf(n-v+1,col[v]);
	ve[y].clear();f[F(y)]=F(x);
}
int main()
{
	cin>>n;pw[0]=1;
	for(int i=1;i<N;i++)pw[i]=pw[i-1]*bas; 
	for(int i=3;i<2*n;i++)cin>>a[i],id[i]=i;
	sort(id+3,id+2*n,[](int X,int Y){return a[X]<a[Y];});
	for(int i=1;i<=n;i++)col[i]=rd()%(bas-1)+1,f[i]=i,ve[i].push_back(i);
	T0.Build(0);T1.Build(1);
	for(int t=3;t<2*n;t++)
	{
		int k=id[t],L=max(k-n,1ll),R=k-L;
		while(1)
		{
			int l=1,r=(k-1)/2-L+1,s=0;
			while(l<=r)!Chk(L,R,mi)?(s=mi,r=mi-1):l=mi+1;
			if(!s)break;
			Mer(L+s-1,R-s+1);ans+=a[k];
		}
	}
	cout<<ans;
}