Minimizing Crossing Pairs

Farmer John raises N breeds of cows, each with its own dedicated field on either side of a long road. One side of the road has fields in a fixed order, while the other side’s fields can be cyclically shifted. When a cow crosses the road, it goes from its field on one side to its matching field on the other side. If the two orderings do not match, the straight‐line paths of cows from different breeds may cross.

A pair of distinct breeds \( (a,b) \) is said to be crossing if every path for breed \(a\) intersects every path for breed \(b\). If the orderings were identical, no crossing would occur. Farmer John can choose a cyclic shift on one side of the road (i.e. move every field \(k\) positions forward with wrap‐around) to reduce the total number of crossing pairs.

Your task is to determine the minimum possible number of crossing pairs after an appropriate cyclic shift.

Details:

• The farm has \(N\) breeds with \(1 \le N \le 100{,}000\).
• The fixed side of the road has a sequence of \(N\) fields described by a permutation \(A\) of \(1, 2, \dots, N\).
• The other side of the road initially has a sequence of \(N\) fields described by a permutation \(B\) of \(1, 2, \dots, N\). You are allowed to perform a cyclic shift by any \(0 \le k < N\) on this side. A cyclic shift by \(k\) means that the field that was originally in position \(j\) (0-indexed) will move to position \((j - k + N) \bmod N\).
• After the cyclic shift, for each breed \(i\), its left field is at position corresponding to its location in \(A\) and its right field is at its new position in \(B\). Two breeds \(a\) and \(b\) (with \(a \neq b\)) form a crossing pair if the segments connecting their fields (from left to right side) intersect, which is equivalent to: either \(A\) orders them one way and the shifted \(B\) orders them the other way.

Help Farmer John determine the minimum number of crossing pairs possible after optimally choosing the cyclic shift.

inputFormat

The input consists of three lines:

1. An integer \(N\) representing the number of cow breeds.
2. \(N\) space-separated distinct integers representing the order of fields on the fixed side (permutation \(A\)).
3. \(N\) space-separated distinct integers representing the order of fields on the shiftable side (permutation \(B\)).

outputFormat

Output a single integer: the minimum number of crossing pairs possible after an optimal cyclic shift of the fields on the shiftable side.

sample

4
1 2 3 4
4 1 2 3

0