营业额统计（SBT）

#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;
}