1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define N 38001 6 #define INF 2147483647 7 #define min(a,b) (((a)<(b))?(a):(b)) 8 struct Point{int v,p;}t[N]; 9 bool operator < (const Point &a,const Point &b){return a.v<b.v;}10 int n,ma[N],a[N],en,sum,sz,l[201],r[201],sumv[201],num[N],b[N],ans;11 inline void R(int &x){12     char c=0;int f=1;13     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1;14     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘);15     x*=f;16 }17 void makeblock()18 {19     sz=sqrt(en); if(!sz) sz=1;20     for(sum=1;sum*sz<en;sum++)21       {22           l[sum]=r[sum-1]+1;23           r[sum]=sz*sum;24           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;25       }26     l[sum]=r[sum-1]+1;27     r[sum]=en;28     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;29 }30 inline void Insert(const int &x){b[x]++; sumv[num[x]]++;}31 inline int Next(const int &x)32 {33     if(b[x]>1) return x;34     for(int i=x+1;i<=r[num[x]];i++) if(b[i]) return i;35     for(int i=num[x]+1;i<=sum;i++) if(sumv[i])36       for(int j=l[i];;j++)37         if(b[j]) return j;38     return INF;39 }40 inline int Pre(const int &x)41 {42     if(b[x]>1) return x;43     for(int i=x-1;i>=l[num[x]];i--) if(b[i]) return i;44     for(int i=num[x]-1;i>=1;i--) if(sumv[i])45       for(int j=r[i];;j--)46         if(b[j]) return j;47     return INF;48 }49 int main()50 {51     R(n); for(int i=1;i<n;i++)52       {53           R(t[i].v);54           t[i].p=i;55       }56     if(scanf("%d",&t[n].v)==EOF) t[n].v=0; t[n].p=n;57     sort(t+1,t+n+1);58     ma[a[t[1].p]=++en]=t[1].v;59     for(int i=2;i<=n;i++)60       {61           if(t[i].v!=t[i-1].v) en++;62           ma[a[t[i].p]=en]=t[i].v;63       } makeblock();64     Insert(a[1]); ans+=ma[a[1]];65     for(int i=2;i<=n;i++)66       {67           Insert(a[i]);68           int Up=Next(a[i]),Down=Pre(a[i]);69           if(Up==INF) ans+=(ma[a[i]]-ma[Down]);70           else if(Down==INF) ans+=(ma[Up]-ma[a[i]]);71         else ans+=min(ma[Up]-ma[a[i]],ma[a[i]]-ma[Down]);72       } printf("%d\n",ans);73     return 0;74 }