//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'

#include <vector>

using namespace std;
//vector<pair<llo,llo>> adj[2*500001];
//llo dist[2*500001];
vector<pair<int,int>> xx;
/*vector<int> cc;
vector<int> dd;*/

llo tree[4*500001];
llo tree2[4*500001];
llo tree3[4*500001];
llo lazy[4*500001];
llo lazy2[4*500001];
//min dist,index
void build(int no,int l,int r){
	////cout<<l<<"::"<<r<<"::"<<no<<endl;
	if(l==r){

		/*if(l==0){
			//cout<<no<<endl;
		}*/
		if(xx[l].b==0){
			tree[no]=0;
		}
		else{
			tree[no]=(llo)1e15;
		}
		tree2[no]=xx[l].a;//max
		tree3[no]=xx[l].a;//min
		lazy[no]=(llo)1e15;
		lazy2[no]=(llo)1e15;
		/*if(no==2){
			//cout<<lazy[no]<<endl;
		}*/
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
		
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
		tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
			lazy[no]=(llo)1e15;
		lazy2[no]=(llo)1e15;

	}
}

llo cd=2e14;
void push(int no,int l,int r){
	//if(tree[no].a>lazy[no]+tree3[no]){}
	//if(no==2){
	//	//cout<<l<<",,"<<r<<",,"<<lazy[no]<<",,"<<lazy2[no]<<endl;
	//}
	if(lazy[no]<cd){
		tree[no]=min(tree[no],lazy[no]+tree3[no]);
		if(l<r){
			lazy[no*2+1]=min(lazy[no*2+1],lazy[no]);
			lazy[no*2+2]=min(lazy[no*2+2],lazy[no]);
		}
		lazy[no]=cd;
	}
	if(lazy2[no]<cd){
		tree[no]=min(tree[no],lazy2[no]-tree2[no]);
		if(l<r){
			lazy2[no*2+1]=min(lazy2[no*2+1],lazy2[no]);
			lazy2[no*2+2]=min(lazy2[no*2+2],lazy2[no]);
		}
		lazy2[no]=cd;
	}
	
}

void update(int no,int l,int r,int aa,int bb,llo cc,int stt){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){

		if(stt==0){
		//	//cout<<l<<",,,"<<r<<endl;
		//	//cout<<tree3[no]<<",,"<<cc<<",,"<<tree[no]<<",,"<<no<<endl;

			tree[no]=min(tree[no],cc+tree3[no]);
		//	//cout<<tree3[no]<<",,"<<cc<<",,"<<tree[no]<<endl;
			if(l<r){
				lazy[no*2+1]=min(lazy[no*2+1],cc);
				lazy[no*2+2]=min(lazy[no*2+2],cc);
			}
		}
		else{
			//cout<<l<<"<"<<r<<",,"<<cc<<",,"<<tree2[no]<<endl;
			tree[no]=min(tree[no],cc-tree2[no]);
			if(l<r){
				lazy2[no*2+1]=min(lazy2[no*2+1],cc);
				lazy2[no*2+2]=min(lazy2[no*2+2],cc);
			}
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,cc,stt);
		update(no*2+2,mid+1,r,aa,bb,cc,stt);
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
//		//cout<<l<<"<"<<r<<"<"<<tree[no]<<endl;

		//tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
	//	tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
	}
	////cout<<l<<"<"<<r<<"<"<<tree[no]<<endl;
}
void update2(int no,int l,int r,int i){
	push(no,l,r);
	if(l==r){
	//	//cout<<l<<":::"<<r<<endl;
		tree[no]=(llo)1e17;
		tree2[no]=-(llo)1e17;
		tree3[no]=(llo)1e17;
		lazy[no]=(llo)1e17;
		lazy2[no]=(llo)1e17;
	}
	else{
		llo mid=(l+r)/2;
		
		
		if(i<=mid){
			update2(no*2+1,l,mid,i);
			push(no*2+2,mid+1,r);
		}
		else{
			update2(no*2+2,mid+1,r,i);
			push(no*2+1,l,mid);
		}

		tree[no]=min(tree[no*2+1],tree[no*2+2]);


		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
		tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
	}
}

void brucia(int n, vector<int> &aa, vector<int> &bb, vector<llo> &tt) {
	//cc=aa;
//	dd=bb;

	for(llo i=0;i<n;i++){
		xx.pb({aa[i],i});
	}
	sort(xx.begin(),xx.end());
	build(0,0,n-1);
	////cout<<lazy[2]<<endl;
	////cout<<tree[2]<<endl;
	map<llo,llo> ind2;
	for(llo i=0;i<n;i++){
		tt[i]=-1;
		//ind2[xx[i].b]=i;
	}
	//for(auto j:xx){
		//cout<<j.a<<",,"<<j.b<<endl;
	//}

	while(true){
		llo ac=tree[0];
		if(ac>(1e9)*n){
			break;
		}
		//cout<<ac<<endl;
		////cout<<tree[2]<<endl;
		////cout<<lazy[2]<<endl;
		int ll=0;
		int rr=n-1;
		int cur=0;
		
	//	pop(0,0,n-1);
		while(ll<rr){
			int mid=(ll+rr)/2;
			push(cur*2+1,ll,mid);
			push(cur*2+2,mid+1,rr);
			if(tree[cur*2+1]==ac){
				rr=mid;
				cur*=2;
				cur+=1;
			}
			else{
				ll=mid+1;
				cur*=2;
				cur+=2;
			}
		}
		//cout<<tree[3]<<"<<"<<tree[4]<<"<<"<<tree[2]<<endl;
		//cout<<ll<<",,"<<rr<<endl;
		update2(0,0,n-1,rr);
			//cout<<tree[3]<<"<<"<<tree[4]<<"<<"<<tree[2]<<endl;
	//	//cout<<tree[2]<<endl;
		int ind=xx[rr].b;
		//cout<<tree[0]<<endl;
		tt[ind]=ac;

		pair<int,int> kkc={min(aa[ind],bb[ind]),0};
		int l=lower_bound(xx.begin(),xx.end(),kkc)-xx.begin();
		kkc={max(aa[ind],bb[ind])+1,0};
		int r=lower_bound(xx.begin(),xx.end(),kkc)-xx.begin()-1;;
		if(aa[ind]<bb[ind]){
			//stt=0;
			update(0,0,n-1,l,r,ac-aa[ind],0);
		}
		else{
			update(0,0,n-1,l,r,ac+aa[ind],1);
		}
		//cout<<endl<<endl;
	}


}