勇敢的骑士来到国王面前请求允许与公主结婚。国王知道骑士很勇敢,但他也想知道他是否足够聪明。于是他请他解决下面的任务。
存在从 1 到 $$$2n$$$ 的数字排列 $$$p_i$$$。您可以进行两种类型的操作。
- 交换 $$$p_1$$$ 和 $$$p_2$$$、$$$p_3$$$ 和 $$$p_4$$$、...、$$$p_{2n-1}$$$ 和 $$$p_{2n}$$$。
- 交换 $$$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:$$$3, 6, 5, 2, 1, 4$$$。
- 进行操作 2:$$$2, 1, 4, 3, 6, 5$$$。
- 执行操作 1:$$$1, 2, 3, 4, 5, 6$$$。