Walk Swapping

A cycle $C$ with $n$ vertices is a graph in which vertices $i$ and $i + 1$ are connected by an edge for $i = 1, \dots, n - 1$, and vertices $n$ and $1$ are connected by an edge. The vertices of $C$ are numbered 1 to $n$.

There are $n$ coins, and each coin is numbered with one of $\{1, 2, \dots, n\}$. Two coins may have the same number. Initially, each vertex of $C$ holds one coin. Two vertices can swap their coins with each other.

For a walk $w = (v_1, v_2, \dots, v_k)$ in $C$, a walk swapping swaps the coins on $v_i$ and $v_{i+1}$ in the order $i = 1, 2, \dots, k - 1$. A walk is a sequence of $k$ ($\geq 1$) vertices in which consecutive vertices are different and adjacent in $C$. You can think of a walk as the vertices visited when you traverse $C$. The number $k$ is the length of $w$. A walk of length $k \geq 2$ causes $k - 1$ swaps, and a walk of length one causes no swap.

The figure below shows the walk swapping for the walk $(2, 1, 4, 1)$ on a cycle with 4 vertices.

For example, the walk $(2, 1, 4, 1)$ in the figure causes 3 swaps. The same final configuration is reached by the walk $(1, 2)$ with only one swap.

You are given the initial and final configurations of coins. Find a walk swapping that turns the initial configuration into the final one with the minimum total number of swaps.

The first line contains an integer $n$ ($1 \leq n \leq 3\,000$), the number of vertices in $C$.

The second line contains $n$ integers between 1 and $n$. The $i$-th integer is the coin on vertex $i$ in the initial configuration. Values may repeat.

The third line contains $n$ integers between 1 and $n$ in the same format, giving the coin on each vertex in the final configuration.

Print exactly one line containing the minimum number of swaps in a walk swapping that turns the initial configuration into the final one. If no walk swapping can do this, print -1.