Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn't have an adjacent number to the left or right, Artem doesn't get any points. 

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai (1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Examples

Input

5
3 1 5 2 6


Output

11


Input

5
1 2 3 4 5


Output

6


Input

5
1 100 101 100 1


Output

102
9
72 49 39 50 68 35 75 94 56
 4
2 3 1 2
 8
3 4 3 1 1 3 4 1
 1
4
 7
2 1 2 2 2 2 2
 6
1 7 3 1 6 2
 8
77 84 26 34 17 56 76 3
 2
93 51
 1
87
 4
86 21 58 60
 10
96 66 8 18 30 48 34 11 37 42
 6
46 30 38 9 65 23
 5
21 6 54 69 32
 3
1 2 1
 3
31 19 5
 10
4 2 2 4 1 2 2 4 2 1
 7
82 60 92 4 2 13 15
 9
4 5 2 2 3 1 3 3 5
 5
2 6 2 1 2
 2
3 1

435 4 15 0 10 12 279 0 0 118 299 145 74 1 5 21 129 23 6 0
using namespace std;
#include<bits/stdc++.h>
//typedef long long   LL;
typedef int   LL;
typedef long long   ll;
typedef   pair<LL,LL>  PII;
typedef   vector< PII > VPII;
typedef   vector<LL>   VI;
typedef   map<string,LL>  MSI;
typedef   map<LL,LL>  MII;
///Print
#define casep(no,val) printf("Case %lld: %lld\n",++no,val)
#define casenl(no) printf("Case %lld:\n",++no)
#define RR(n,m)       scanf("%lld%lld", &n,&m)
#define case(no) printf("Case %lld: ",++no)
#define R(n)       scanf("%lld", &n)
#define P(a)  printf("%lld\n",a)
#define NL printf("\n")
///LOOP
#define FORSTL(x,n) for(__typeof(n.begin()) x=n.begin();x!=n.end();x++)
#define repp(x,n) for(__typeof(n) x=1;x<=(n);x++)
#define reps(i,x) for(int  i=0;i<(x.size());i++)
#define rep(x,n) for(__typeof(n) x=0;x<(n);x++)
///Shortcut
#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin())
#define fastinput ios_base::sync_with_stdio(false); cin.tie(false);
#define mem(ar,value) memset(ar,value,sizeof(ar))
#define all(x) x.begin(),x.end()
#define len(s) s.size()
#define mp make_pair
#define pb push_back
#define SS second
#define FF first
///Binary_search
#define LB(a,x) (lower_bound(all(a),x)-a.begin())
#define UB(a,x) (upper_bound(all(a),x)-a.begin())
///Min AND Max
#define isEq(a,b) (fabs((a)-(b))<eps)
#define MIN3(a,b,c) min(a,min(b,c))
#define MAX3(a,b,c) max(a,max(b,c))
#define PI acos(-1.0)
#define EPS (1e-9)
///DEBUG
#define DDD(x,y,z) cerr<<__FUNCTION__<<":"<<__LINE__<<": "#x" = "<<x<<" | "#y" = "<<y<<" | "#z" ="<<z<<endl;
#define DD(x,y) cerr<<__FUNCTION__<<":"<<__LINE__<<": "#x" = "<<x<<" | "#y" = "<<y<<endl;
#define D(x) cerr<<__FUNCTION__<<":"<<__LINE__<<": "#x" = "<<x<<endl;

///Gcd and Lcm
template<class T>T gcd(T a,T b){return b == 0 ? a : gcd(b, a % b);}
template<typename T>T lcm(T a, T b) {return a / gcd(a,b) * b;}
///Bigmod && Pow
template<class T>T my_pow(T n,T p){if(p==0)return 1;T x=my_pow(n,p/2);x=(x*x);if(p&1)x=(x*n);return x;} ///n to the power p
template<class T>T big_mod(T n,T p,T m){if(p==0)return (T)1;T x=big_mod(n,p/2,m);x=(x*x)%m;if(p&1)x=(x*n)%m;return x;}
///string to int
template <class T> T extract(string s, T ret) {stringstream ss(s); ss >> ret; return ret;}///
string itos(LL n){string s;while(n){s+=(n%10+48);n/=10;}reverse(all(s));return s;}
LL stoi(string s){LL n=0;rep(i,len(s))n=n*10+(s[i]-48);return n;}
/// geometry
double DEG(double x) { return (180.0*x)/(PI);}
double RAD(double x) { return (x*(double)PI)/(180.0);}
template<typename T> T DIS(T x1,T y1,T x2, T y2){return sqrt( (double)( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) );}
template<typename T> T ANGLE(T x1,T y1,T x2, T y2){ return atan( double(y1-y2) / double(x1-x2));}
template<typename T> LL isLeft(T a,T b,T c) { return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); }
const  int N=5e5+5,MOD=1e9+7;

//struct info{LL x,y;}arr[N];bool com(info a,info b){return (a.x<b.x) or (a.x==b.x and a.y<b.y);}
LL ar[N];LL a=0,b=0,c=0,r=0,rr=0,res=0,n,m;
//string  s;


struct info
{
    LL x,y;
}T[3*N];

void insert(LL idx,LL st,LL end)
{
    if(st==end)
    {
        T[idx].x=ar[st];
        T[idx].y=st;
        return ;
    }

    LL mid=(st+end)>>1,lf=idx*2,rg=lf+1;
    insert(lf,st,mid);
    insert(rg,mid+1,end);

    if(T[lf].x<T[rg].x)  T[idx]=T[lf];
    else  T[idx]=T[rg];
    return ;
}



void up(LL idx,LL st,LL end,LL pos,LL val)
{
    if(st==pos  and end==pos)
    {
        T[idx].x=val;
       // T[idx].y=st;
        return ;
    }
    LL mid=(st+end)>>1,lf=idx*2,rg=lf+1;


    if(pos<=mid)
    up(lf,st,mid,pos,val);
    else
    up(rg,mid+1,end,pos,val);
    if(T[lf].x<T[rg].x)  T[idx]=T[lf];
    else  T[idx]=T[rg];
    return ;
}





info read(LL idx,LL st,LL end,LL i,LL j)
{
    if(st==i  and end==j)
    {
        return T[idx];
    }
    LL mid=(st+end)>>1,lf=idx*2,rg=lf+1;
    if(j<=mid)
    return read(lf,st,mid,i,j);
    else if(i>mid)  return read(rg,mid+1,end,i,j);

    else
    {
        info aa=read(lf,st,mid,i,mid);
        info bb= read(rg,mid+1,end,mid+1,j);
        if(aa.x<bb.x)  return aa;
        else  return bb;
    }

}



LL par[N][2];
LL find(LL idx,LL f)
{
    if(idx==par[idx][f])  return idx;
    else    return par[idx][f]=find(par[idx][f],f);
}



int main()
{
   fastinput;

    cin>>n;  repp(i,n)  cin>>ar[i];

    insert(1,1,n);


   // D(read(1,1,n,1,n).y);


    repp(i,n+2)  par[i][0]=i;
    repp(i,n+2)  par[i][1]=i;


    repp(i,n-2)
    {

        LL aa=read(1,1,n,1,n).y;
        LL bb=find(aa,0);
        LL cc=find(aa,1);
        LL dd=find(bb-1,0);
        LL ee=find(cc+1,1);


        par[bb][0]=dd;
        par[cc][1]=ee;


       if(min(ar[dd],ar[ee])==0)  r+=ar[aa];
       else  r+=min(ar[dd],ar[ee]);
        up(1,1,n,aa,10000000);






    }


    cout<<r<<"\n";



   return 0;

}
