Cyclic Shifts — Eolymp

Input

The first line contains an integer $n$ ( $1 \leq n \leq 5000$ 1 \leq n \leq 5000) — the length of the permutations.

The second line contains $n$ pairwise distinct integers $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) — permutation $a$ .

The third line contains $n$ pairwise distinct integers $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) — permutation $b$ .

Output

Print one integer — the minimum total number of operations needed so that for every $k$ from $1$ to $n$ , the sum of the first $k$ elements of permutation $a$ is not less than the sum of the first $k$ elements of permutation $b$ .

Examples

Example 1

Loading

Example 2

Loading

Note

In the first example, the condition is already satisfied without any operations, so the answer is $0$ .

In the second example, you can cyclically shift permutation $a$ twice and permutation $b$ once:

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

After that, the prefix sums of permutation $a$ are $3, 7, 8, 10$ 3, 7, 8, 10, and those of permutation $b$ are $2, 6, 7, 10$ 2, 6, 7, 10. Thus, all required inequalities hold.

It is impossible to achieve this in fewer than $3$ operations, so the answer is $3$ .

Scoring

Subtask $1$ ( $25$ points): $n \leq 8$ n \le 8.
Subtask $2$ ( $50$ points): $n \leq 100$ n \le 100.
Subtask $3$ ( $85$ points): $n \leq 1000$ n \le 1000.
Subtask $4$ ( $140$ points): No additional constraints.