← 返回题目列表

Codeforces · 1510/K

K. 国王的任务

中文机器翻译题面 查看原题

勇敢的骑士来到国王面前请求允许与公主结婚。国王知道骑士很勇敢,但他也想知道他是否足够聪明。于是他请他解决下面的任务。

存在从 1 到 $$$2n$$$ 的数字排列 $$$p_i$$$。您可以进行两种类型的操作。

  1. 交换 $$$p_1$$$ 和 $$$p_2$$$、$$$p_3$$$ 和 $$$p_4$$$、...、$$$p_{2n-1}$$$ 和 $$$p_{2n}$$$。
  2. 交换 $$$p_1$$$ 和 $$$p_{n+1}$$$、$$$p_2$$$ 和 $$$p_{n+2}$$$、...、$$$p_{n}$$$ 和 $$$p_{2n}$$$。

任务是找到对给定排列进行排序所需的最少操作数。

骑士其实并不那么聪明,但是很有魅力,所以公主请你帮助他解决国王的任务。

输入

第一行包含整数 $$$n$$$ ($$$1\le n\le 1000$$$)。第二行包含 $$$2n$$$ 整数 $$$p_i$$$ — 从 1 到 $$$2n$$$ 的数字排列。

输出

打印一个整数——对排列进行排序所需的最少操作数。如果无法使用这些操作对排列进行排序,请打印 $$$-1$$$。

示例

输入
复制

3
6 3 2 5 4 1

输出
复制

3

输入
复制

2
3 4 2 1

输出
复制

-1

输入
复制

4
1 2 3 4 5 6 7 8

输出
复制

0

注意

在第一个示例中,您可以通过三个操作对排列进行排序:

  1. 执行操作 1:$$$3, 6, 5, 2, 1, 4$$$。
  2. 进行操作 2:$$$2, 1, 4, 3, 6, 5$$$。
  3. 执行操作 1:$$$1, 2, 3, 4, 5, 6$$$。