Description

There is a $2 \times n$ table, filled with the numbers $1 \sim 2 \times n$ with no repetition and nothing missing. You may perform several operations. In each operation, you can choose a $2 \times 2$ square area and then rotate it by $180\degree$.

Given the current state and the target state, determine whether the target state can be reached. If it can, output the minimum number of operations.

Input Format

The first line contains a positive integer $n$.

The next two lines each contain $n$ positive integers, describing the current state of the table.

The next two lines each contain $n$ positive integers, describing the target state of the table.

Output Format

If there is no solution, output one line dldsgay!!1.

Otherwise, output one integer, the minimum number of operations.

1
1
2
2
1

dldsgay!!1

2
1 2
3 4
4 3
2 1

1

2
1 2
3 4
1 2
4 3

dldsgay!!1

3
1 6 2
4 3 5
2 4 3
5 1 6

2

Hint

Subtasks

This problem uses bundled testdata.

For $100\%$ of the testdata: $1 \leq n \leq 10^6$.

This problem has $10$ subtasks. The score and constraints of each subtask are as follows:

Subtask $1$ ($1$ point): It is guaranteed that the output must be dldsgay!!1.
Subtask $2$ ($1$ point): It is guaranteed that the target state is the same as the current state.
Subtask $3$ ($4$ points): $n = 1$.
Subtask $4$ ($5$ points): $n = 2$.
Subtask $5$ ($14$ points): $1 \leq n \leq 20$.
Subtask $6$ ($19$ points): $1 \leq n \leq 100$.
Subtask $7$ ($19$ points): $1 \leq n \leq 1000$.
Subtask $8$ ($8$ points): It is guaranteed that the first row of the target state is $1 \sim n$ in order, and the second row is $n + 1 \sim 2n$ in order.
Subtask $9$ ($10$ points): It is guaranteed that there is no unsolvable case.
Subtask $10$ ($19$ points): No special constraints.

Translated by ChatGPT 5