King's Task

Interview

Time limit3sMemory limit512 MB

Summary

Given a permutation of 1 to 2n, find the fewest swaps of adjacent pairs or of the two halves needed to sort it, or report that sorting is impossible.

Level: Medium6 of 10
Topics: Graph, BFS, Simulation, Implementation
Solved: No attempts yet

Problem

A brave knight came to the king and asked for permission to marry the princess. The king knew the knight was brave, but he also wanted to know whether he was smart enough. So he gave him the following task.

There is a permutation $p_i$ of the numbers from 1 to $2n$ . You can perform two types of operations.

Swap $p_1$ and $p_2$ , $p_3$ and $p_4$ , ..., $p_{2n-1}$ and $p_{2n}$ .
Swap $p_1$ and $p_{n+1}$ , $p_2$ and $p_{n+2}$ , ..., $p_{n}$ and $p_{2n}$ .

The task is to find the minimum number of operations needed to sort the given permutation.

The knight was not that smart, but he was charming, so the princess asks you to help him solve the king's task.

Input

The first line contains the integer $n$ ( $1\le n\le 1000$ ). The second line contains $2n$ integers $p_i$ , the permutation of the numbers from 1 to $2n$ .

Output

Print one integer, the minimum number of operations needed to sort the permutation. If the permutation cannot be sorted with these operations, print $-1$ .

Hint

In the first example, the permutation can be sorted in three operations:

Perform operation 1: $3, 6, 5, 2, 1, 4$ .
Perform operation 2: $2, 1, 4, 3, 6, 5$ .
Perform operation 1: $1, 2, 3, 4, 5, 6$ .

Examples3

Example 1
Input
```
3
6 3 2 5 4 1
```
Expected output
```
3
```
Example 2
Input
```
2
3 4 2 1
```
Expected output
```
-1
```
Example 3
Input
```
4
1 2 3 4 5 6 7 8
```
Expected output
```
0
```