Topic Description
Tiger was recently promoted to business manager. After taking office, his first task was to count and analyze the business situation of the company since its establishment.
Tiger took out the company's books, which recorded the company's daily turnover since its inception. Analyzing the business situation is a rather complicated task. Because of holidays, big price reductions or other circumstances, there will be certain fluctuations in turnover, of course, certain fluctuations are acceptable, but in some cases turnover changes very high or very low, which proves that the company's business situation at this time has been a problem. In economic management, a minimum fluctuation value is defined to measure this situation.
The greater the minimum volatility, the more unstable the business situation is.
And to analyze whether the whole company's business situation is stable from its inception to the present, we only need to add up the smallest fluctuations of every day. Your task is to write a program to help Tiger calculate this value.
The minimum volatility of the first day is the turnover of the first day.
Input and output format
Input format:
The input is read in by the file'turnover.in'.
The first positive integer n (n <= 32767) indicates the number of days the company has been established until now, and the next N lines have an integer AI (| AI |<== 1000000) for each line, indicating that the company's turnover on the first day may be negative.
Output format:
Input and Output Samples
Input sample #1:
6
5
1
2
5
4
6
Output sample #1:
12
Explain
The results show that: 5+ | 1-5 |+ | 2-1 | + | | 5-5 | + | 4-5 | + | | 6-5 | = 5 + 4 + 1 + 0 + 1 + 1 = 12

//Each query is greater than his minimum, and less than his maximum.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN 50010
#define INF 0x7fffffff
int a[MAXN],d[MAXN],n;
struct Data{ int val,ord; }data[MAXN];
bool cmp(Data a,Data b){ return a.val < b.val; }
struct Seg_Tree{ int l,r,sum,Max,Min; }tre[MAXN<<2];
void UpDate(int u){
    tre[u].sum=tre[u<<1].sum+tre[u<<1|1].sum;
    tre[u].Max=max(tre[u<<1].Max,tre[u<<1|1].Max);
    tre[u].Min=min(tre[u<<1].Min,tre[u<<1|1].Min);
}
void Build(int u,int l,int r){
    tre[u].l=l;tre[u].r=r;
    tre[u].Max=-1;tre[u].Min=INF-1;
    if(l==r) return ;
    int Mid=(l+r)>>1;
    if(l<=Mid) Build(u<<1,l,Mid);
    if(r>Mid) Build(u<<1|1,Mid+1,r);
}
void Modify(int u,int pos){
    if(tre[u].l==tre[u].r){
        tre[u].sum=1;
        tre[u].Max=tre[u].l;
        tre[u].Min=tre[u].l;
        return;
    }
    int Mid=(tre[u].l+tre[u].r)>>1;
    if(pos<=Mid) Modify(u<<1,pos);
    if(pos>Mid) Modify(u<<1|1,pos);
    UpDate(u);
}
int Query_Max(int u,int l,int r){
    if(r<l) return -1;
    if(tre[u].sum==0) return -1;
    if(l<=tre[u].l&&tre[u].r<=r) return tre[u].Max;
    int Mid=(tre[u].l+tre[u].r)>>1,ret=-2;
    if(l<=Mid) ret=max(ret,Query_Max(u<<1,l,r));
    if(r>Mid)ret=max(ret,Query_Max(u<<1|1,l,r));
    return ret;
}
int Query_Min(int u,int l,int r){
    if(r<l) return INF-1;
    if(tre[u].sum==0) return INF-1;
    if(l<=tre[u].l&&tre[u].r<=r) return tre[u].Min;
    int Mid=(tre[u].l+tre[u].r)>>1,ret=INF;
    if(l<=Mid) ret=min(ret,Query_Min(u<<1,l,r));
    if(r>Mid)ret=min(ret,Query_Min(u<<1|1,l,r));
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        if(scanf("%d",&a[i])==EOF) a[i]=0;
        data[i].ord=i;data[i].val=a[i];
    }
    sort(data+1,data+1+n,cmp);
    int ord=1;d[1]=data[1].val;a[data[1].ord]=ord;
    for(int i=2;i<=n;i++){
        if(data[i].val!=data[i-1].val) ord++;
        a[data[i].ord]=ord;d[ord]=data[i].val;
    }
    Build(1,1,ord);
    int ans=d[a[1]];Modify(1,a[1]);
    for(int i=2;i<=n;i++){
        int x=Query_Max(1,1,a[i]-1),y=Query_Min(1,a[i],n),tmp=INF;
        if(x!=-1) tmp=min(tmp,d[a[i]]-d[x]);
        if(y!=INF-1) tmp=min(tmp,d[y]-d[a[i]]);
        ans+=tmp;
        Modify(1,a[i]);
    }
    printf("%d\n",ans);
    return 0;
}