https://www.luogu.com.cn/record/126682902

sub1一个点wa了，应该不是什么大问题，不知道被什么东西hack了

#include<bits/stdc++.h>
#define ll int
using namespace std;
const int N=1e5+10,inf=1e9;
int n,rt,idx;
struct Node{
	int l,r,key,val,cnt,sz;
}tr[N];
int get_node(int key){
	tr[++idx].key=key;
	tr[idx].val=rand();
	tr[idx].cnt=tr[idx].sz=1;
	return idx;
}
void pushup(int p){
	tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt;
}
void zig(int &p){
	int q=tr[p].l;
	tr[p].l=tr[q].r,tr[q].r=p,p=q;
	pushup(p);pushup(tr[p].r);
}
void zag(int &p){
	int q=tr[p].r;
	tr[p].r=tr[q].l,tr[q].l=p,p=q;
	pushup(p);pushup(tr[p].l);
}
void build(){
	get_node(-inf);get_node(inf);
	tr[1].r=2;rt=1; 
	pushup(rt);
	if(tr[1].val<tr[2].val) zag(rt);
}
void insert(int &p,int key){
	if(!p) p=get_node(key);
	else if(tr[p].key==key) tr[p].cnt++;
	else if(tr[p].key>key){
		insert(tr[p].l,key);
		if(tr[tr[p].l].val>tr[p].val) zig(p);
	}
	else{
		insert(tr[p].r,key);
		if(tr[tr[p].r].val>tr[p].val) zag(p); 
	}
	pushup(p);
}
ll get_prev(int p,int key){
	if(!p) return -inf; 
	else if(tr[p].key>key) return get_prev(tr[p].l,key);
	return max(tr[p].key,get_prev(tr[p].r,key)); 
}
ll get_next(int p,int key){
	if(!p) return inf;
	else if(tr[p].key<key) return get_next(tr[p].r,key);
	return min(tr[p].key,get_next(tr[p].l,key));
} 
int main(){
	scanf("%d",&n);ll x,res=0;
	build();
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		if(i==1) res+=x;
		else{
			ll t1=get_next(rt,x),t2=get_prev(rt,x);
			res+=min(abs(x-t1),abs(x-t2));
		}
		insert(rt,x);
	}
	printf("%lld",res);
    return 0;
}