Kyoto University decided to build a straight wall on the west side of the university to protect against gorillas that attack the university from the west every night. Since it is difficult to protect the university at some points along the wall where gorillas attack violently, reinforcement materials are also built at those points. Although the number of the materials is limited, the state-of-the-art technology can make a prediction about the points where gorillas will attack next and the number of gorillas that will attack at each point. The materials are moved along the wall everyday according to the prediction. You, a smart student majoring in computer science, are called to find the way to move the materials more efficiently.

Theare are N points where reinforcement materials can be build along the straight wall. They are numbered 1 through N. Because of the protection against the last attack of gorillas, A_i materials are build at point i (1 \leq i \leq N). For the next attack, the materials need to be rearranged such that at least B_i materials are built at point i (1 \leq i \leq N). It costs |i - j| to move 1 material from point i to point j. Find the minimum total cost required to satisfy the condition by moving materials. You do not need to consider the attack after the next.

Constraints

* 1 \leq N \leq 10^5
* A_i \geq 1
* B_i \geq 1
* A_1 + A_2 + ... + A_N \leq 10^{12}
* B_1 + B_2 + ... + B_N \leq A_1 + A_2 + ... + A_N
* There is at least one way to satisfy the condition.

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

Print the minimum total cost required to satisfy the condition.

Partial Scores

30 points will be awarded for passing the test set satisfying the following:

* N \leq 100
* A_1 + A_2 + ... + A_N \leq 400



Another 30 points will be awarded for passing the test set satisfying the following:

* N \leq 10^3



Another 140 points will be awarded for passing the test set without addtional constraints and you can get 200 points in total.

Examples

Input

2
1 5
3 1


Output

2


Input

5
1 2 3 4 5
3 3 1 1 1


Output

6


Input

27
46 3 4 2 10 2 5 2 6 7 20 13 9 49 3 8 4 3 19 9 3 5 4 13 9 5 7
10 2 5 6 2 6 3 2 2 5 3 11 13 2 2 7 7 3 9 5 13 4 17 2 2 2 4


Output

48


Input

18
3878348 423911 8031742 1035156 24256 10344593 19379 3867285 4481365 1475384 1959412 1383457 164869 4633165 6674637 9732852 10459147 2810788
1236501 770807 4003004 131688 1965412 266841 3980782 565060 816313 192940 541896 250801 217586 3806049 1220252 1161079 31168 2008961


Output

6302172


Input

2
1 99999999999
1234567891 1


Output

1234567890
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<class V,int NV> class SegTree_3 {
public:
	vector<pair<V,int> > val;
	vector<pair<V,int> > ma;
	static V const def=1LL<<50;
	SegTree_3(){
		int i;
		val.resize(NV*2); ma.resize(NV*2);
		FOR(i,NV) val[i+NV]=ma[i+NV]=make_pair(0,i);
		FOR(i,NV) val[i]=make_pair(0,0);
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,0);
		if(x<=l && r<=y) return ma[k];
		auto a=min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		a.first += val[k].first;
		return a;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k].first+=v;
			ma[k].first+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=min(ma[k*2],ma[k*2+1]);
			ma[k].first += val[k].first;
		}
	}
};
int N;
ll A[101010];
ll B[101010];
ll SA[101010];
ll SB[101010];

SegTree_3<ll,1<<19> D,F;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		SA[i+1]=SA[i]+A[i];
	}
	ll ret=0;
	FOR(i,N) {
		cin>>B[i];
		SB[i+1]=SB[i]+B[i];
		if(SA[i+1]>SB[i+1]) {
			F.update(i,i+1,SA[i+1]-SB[i+1]);
			D.update(0,i+1,-1);
		}
		else {
			F.update(i,i+1,1LL<<50);
			D.update(0,i+1,1);
		}
		ret += abs(SB[i+1]-SA[i+1]);
	}
	
	ll flow=SA[N]-SB[N];
	while(flow) {
		
		while(1) {
			auto f=F.getval(0,N);
			if(f.first>0) break;
			D.update(0,f.second+1,2);
			F.update(f.second,f.second+1,1LL<<50);
		}
		//FOR(i,N) _P("%lld/%lld ",D.getval(i,i+1).first,F.getval(i,i+1).first);
		
		auto p = D.getval(0,N);
		if(p.first>=1LL<<40 || p.first==0) break;
		
		ll d = min(flow,F.getval(p.second,N).first);
		//_P(" : %lld:%d %lld\n",p.first,p.second,d);
		
		ret += p.first*d;
		flow-=d;
		F.update(p.second,N,-d);
	}
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}
