2020-2021 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
K. King's Task

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThe brave Knight came to the King and asked permission to marry the princess. The King knew that the Knight was brave, but he also wanted to know if he was smart enough. So he asked him to solve the following task.

There is a permutation $$$p_i$$$ of numbers from 1 to $$$2n$$$. You can make 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 minimal number of operations required to sort the given permutation.

The Knight was not that smart actually, but quite charming, so the princess asks you to help him to 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 numbers from 1 to $$$2n$$$.

Output

Print one integer — the minimal number of operations required to sort the permutation. If it is impossible to sort the permutation using these operations, print $$$-1$$$.

Examples

Input

3 6 3 2 5 4 1

Output

3

Input

2 3 4 2 1

Output

-1

Input

4 1 2 3 4 5 6 7 8

Output

0

Note

In the first example, you can sort the permutation in three operations:

- Make operation 1: $$$3, 6, 5, 2, 1, 4$$$.
- Make operation 2: $$$2, 1, 4, 3, 6, 5$$$.
- Make operation 1: $$$1, 2, 3, 4, 5, 6$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/25/2021 00:45:12 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|