Circular Hay Bale Balancing

Farmer John recently received a large number of hay bales which were delivered in N piles arranged in a circle. Originally, each pile i was supposed to have B_i bales. However, after the delivery the piles contain A_i bales, respectively. Since the sum of the A_i's equals the sum of the B_i's, Farmer John can move bales between piles, but he cannot buy or remove any bales.

Moving one hay bale from one pile to another that is x steps away (following the circular order) costs x units of work. Your task is to determine the minimum amount of work required to rearrange the bales from the current configuration (A_i) to the target configuration (B_i).

Hint: Define d[i] = A[i] - B[i]. Since \(\sum d[i] = 0\), you can compute cumulative sums along the circle. Let \(P[0]=0\) and \(P[i]=d[0]+d[1]+...+d[i-1]\) for \(i=1,2,...,N\). Finding an appropriate offset (specifically the median of the \(P[i]\)'s) minimizes the total cost which is given by \(\sum_{i=0}^{N-1} |P[i]-m|\), where \(m\) is the median of \(P[0],P[1],...,P[N-1]\).

inputFormat

The input consists of three lines.
The first line contains a single integer N (1 ≤ N ≤ 100,000) which is the number of piles.
The second line contains N space-separated integers representing the current number of hay bales, A₁, A₂, ..., A_N.
The third line contains N space-separated integers representing the desired number of hay bales, B₁, B₂, ..., B_N.
It is guaranteed that \(\sum_{i=1}^N A_i = \sum_{i=1}^N B_i\).

outputFormat

Output a single integer, the minimum total cost (work units) needed to rearrange the hay bales into the desired configuration.

sample

3
1 2 3
2 2 2

1