Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值 = min {该天以前某一天的营业额 - 该天营业额}

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

天数小于100000.

第一行为正整数 ，表示该公司从成立一直到现在的天数

接下来的n行每行有一个整数(一定有数据小于〇) ，表示第i天公司的营业额。

输出文件仅有一个正整数，即每一天的最小波动值之和。答案保证在int范围内

#include<cstdio>

#include<cstring>

#include<string>

#include<cstdlib>

using namespace std;

#define MAXN 100005

#define INF 10000000

int sz[MAXN],ch[MAXN][2],val[MAXN],root,fa[MAXN],n,cnt;

#define abs(a) ((a)>0?(a):-(a))

void rotato(int &r,bool flag)

{

	int t=ch[r][!flag];

	if(!t)return;

	ch[r][!flag]=ch[t][flag];

	ch[t][flag]=r;

	sz[r]=sz[ch[r][0]]+sz[ch[r][1]]+1;

	sz[t]=sz[ch[t][0]]+sz[ch[t][1]]+1;

	r=t;

}

void maintain(int &r,bool flag)

{

	if(!flag)

	{

		if(sz[ch[ch[r][0]][0]]>sz[ch[r][1]])

			rotato(r,1);

		else if(sz[ch[ch[r][0]][1]]>sz[ch[r][1]])

		{

			rotato(ch[r][0],0);

			rotato(r,1);

		}

		else return;

	}

	else

	{

		if(sz[ch[ch[r][1]][1]]>sz[ch[r][0]])

			rotato(r,0);

		else if(sz[ch[ch[r][1]][0]]>sz[ch[r][0]])

		{rotato(ch[r][1],1);

		 rotato(r,0);

		}

		else return;

	}

	maintain(ch[r][0],0);

	maintain(ch[r][1],1);

	maintain(r,0);

	maintain(r,1);

}

void insert(int &r,int t)

{

	if(!r)

	{

		cnt++;

		val[cnt]=t;

		sz[cnt]=1;

		r=cnt;

		return;

	}

	if(val[r]==t)

		return;

	else if(val[r]>t)

	insert(ch[r][0],t);

	else insert(ch[r][1],t);

		maintain(r,t>=val[r]);

}

int find(int r,int t)

{

	int ans=INF;

    while(r)

	{

		if(abs(val[r]-t)<ans)

			ans=abs(val[r]-t);

		if(t<val[r])

			r=ch[r][0];

		else if(t>val[r])

			r=ch[r][1];

		else

            break;

	}

	return ans;

}

int main()

{

	int t,ans=0;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&t);

		if(i>1)

			{

			    int tmp=find(root,t);

                ans+=tmp;

			}

		else ans=t;

		insert(root,t);

	}

	printf("%d\n",ans);

	return 0;

}

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

#define MAXN 100005

#define INF 123456789

int ans,tmpdiff=INF,cnt,root,dayv;

struct node

{

  int lch,rch,num,h;

}tree[MAXN];

int sum;

int n,m;

void zig(int &r)

{

    int t=tree[r].lch;

    tree[r].lch=tree[t].rch;

    tree[t].rch=r;

    tree[r].h=max(tree[tree[r].lch].h,tree[tree[r].rch].h)+1;

    tree[t].h=max(tree[tree[t].lch].h,tree[tree[t].rch].h)+1;

    r=t;

}

void zag(int &r)

{

    int t=tree[r].rch;

    tree[r].rch=tree[t].lch;

    tree[t].lch=r;

    tree[r].h=max(tree[tree[r].lch].h,tree[tree[r].rch].h)+1;

    tree[t].h=max(tree[tree[t].lch].h,tree[tree[t].rch].h)+1;

    r=t;

}

void insert(int &root,int x)

{

    if(root==0)

    {

        tree[++cnt].num=x;

        tree[cnt].h=1;

        root=cnt;

        return;

    }

    tmpdiff=min(tmpdiff,abs(x-tree[root].num));

    if(x<tree[root].num)

        insert(tree[root].lch,x);

    else if(x>tree[root].num)

        insert(tree[root].rch,x);

    else return;

    tree[root].h=max(tree[tree[root].lch].h,tree[tree[root].rch].h)+1;

    if(tree[tree[root].lch].h-tree[tree[root].rch].h>1)

    {

        if(x<tree[tree[root].lch].num)

        {

            zig(root);

        }

        else

        {

            zag(tree[root].lch);

            zig(root);

        }

    }

    else if(tree[tree[root].rch].h-tree[tree[root].lch].h>1)

    {

        if(x>tree[tree[root].rch].num)

            zag(root);

        else

            {

                zig(tree[root].rch);

                zag(root);

            }

    }

    tree[root].h=max(tree[tree[root].lch].h,tree[tree[root].rch].h)+1;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&dayv);

        if(i==1)ans+=dayv;

        tmpdiff=INF;

        insert(root,dayv);

        if(tmpdiff!=INF)

        ans+=tmpdiff;

    }

    printf("%d",ans);

    return 0;

}