Циклічні зсуви

Вхідні дані

У першому рядку міститься ціле число $n$ ( $1 \leq n \leq 5000$ 1 \leq n \leq 5000) — довжина перестановок.

У другому рядку містяться $n$ попарно різних цілих чисел $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) — перестановка $a$ .

У третьому рядку містяться $n$ попарно різних цілих чисел $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) — перестановка $b$ .

Вихідні дані

Виведіть одне ціле число — мінімальну сумарну кількість операцій, яку потрібно виконати, щоб для кожного $k$ від $1$ до $n$ сума перших $k$ елементів перестановки $a$ була не меншою за суму перших $k$ елементів перестановки $b$ .

Приклади

Приклад 1

Loading

Приклад 2

Loading

Примітка

У першому прикладі умова вже виконується без жодної операції, тому відповідь дорівнює $0$ .

У другому прикладі можна двічі циклічно зсунути перестановку $a$ та один раз перестановку $b$ :

[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].

Після цього префіксні суми перестановки $a$ дорівнюють $3, 7, 8, 10$ 3, 7, 8, 10, а перестановки $b$ — $2, 6, 7, 10$ 2, 6, 7, 10. Отже, всі необхідні нерівності виконуються.

Неможливо досягти цього менш ніж за $3$ операції, тому відповідь дорівнює $3$ .

Оцінювання

Підзадача $1$ ( $25$ балів): $n \leq 8$ n \le 8.
Підзадача $2$ ( $50$ балів): $n \leq 100$ n \le 100.
Підзадача $3$ ( $85$ балів): $n \leq 1000$ n \le 1000.
Підзадача $4$ ( $140$ балів): Без додаткових обмежень.