#P6502. Problem C. Shuffle And Modify
Problem C. Shuffle And Modify
Problem Description
Give A and B, both are permutations of [1, 2 × n]. You want to change A to B in minimal moves.
For each move, you can do one of these two operations:
1. Shuffle the A. We define the shuffle as shuffle(A) = $A_1$ $A_{n+1}$ $A_2$ $A_{n+2}$ ... $A_n$$A_{2×n}$
2. Modify one element in A to any number.
Input
Input is given from Standard Input in the following format:
n
$A_1$ $A_2$ ... $A_{2×n}$
$B_1$ $B_2$ ... $B_{2×n}$
Constraints
1 ≤ n ≤ 100000
1 ≤$A_i$, $B_i$ ≤ 2 × n. All $A_i$ are distinct, so do B.
Output
Print one number denotes the minimal moves.
2
1 2 3 4
1 3 2 4
1