Desplazamientos cíclicos

Entrada

La primera línea contiene un entero $n$ ( $1 \leq n \leq 5000$ 1 \leq n \leq 5000) — la longitud de las permutaciones.

La segunda línea contiene $n$ enteros distintos por pares $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — la permutación $a$ .

La tercera línea contiene $n$ enteros distintos por pares $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n ( $1 \leq b_{i} \leq n$ 1 \leq b_i \leq n) — la permutación $b$ .

Salida

Imprime un entero — el mínimo número total de operaciones necesarias para que, para todo $k$ de $1$ a $n$ , la suma de los primeros $k$ elementos de la permutación $a$ no sea menor que la suma de los primeros $k$ elementos de la permutación $b$ .

Ejemplos

Ejemplo 1

Loading

Ejemplo 2

Loading

Nota

En el primer ejemplo, la condición ya se cumple sin realizar ninguna operación, así que la respuesta es $0$ .

En el segundo ejemplo, puedes desplazar cíclicamente la permutación $a$ dos veces y la permutación $b$ una vez:

[1, 2, 3, 4] \to [3, 4, 1, 2],

[1, 2, 3, 4] \rightarrow [3, 4, 1, 2],

[3, 2, 4, 1] \to [2, 4, 1, 3] .

[3, 2, 4, 1] \rightarrow [2, 4, 1, 3].

Después de eso, las sumas prefijas de la permutación $a$ son $3, 7, 8, 10$ 3, 7, 8, 10, y las de la permutación $b$ son $2, 6, 7, 10$ 2, 6, 7, 10. Por lo tanto, todas las desigualdades requeridas se cumplen.

Es imposible lograr esto en menos de $3$ operaciones, así que la respuesta es $3$ .

Puntuación

Subtarea $1$ ( $25$ puntos): $n \leq 8$ n \le 8.
Subtarea $2$ ( $50$ puntos): $n \leq 100$ n \le 100.
Subtarea $3$ ( $85$ puntos): $n \leq 1000$ n \le 1000.
Subtarea $4$ ( $140$ puntos): Sin restricciones adicionales.