You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Swap and Flip

题目描述

现在有$n$张从$1$编号到$n$的卡片，卡片$i$上一面有一个红色写的整数$A_i$，另一面有一个蓝色写的整数$B_i$，一开始，这些卡牌红色面朝上，被从左往右按$1$到$N$的顺序放好。

通过重复下面的操作，请确定是否可以形成一个从左到右朝上的不下降序列（对于每个$i$，左数第$i+1$张卡片朝上的数不小于左数第$i$张卡片朝上的数）。如果可以，那么请计算最小需要的操作次数。如果不可能，请输出-1。

• 选择一个整数$i$，调换左数第$i$张和第$i+1$张卡片，并同时翻转它们。

输入格式

第一行一个整数 $n$ ，第二行 $n$ 个整数 $A_i$ ，第三行 $n$ 个整数 $B_i$ 。

输出格式

一个整数表示最小操作次数，不可能则输出 $-1$ 。

样例 #1

样例输入 #1

3
3 4 3
3 2 3

样例输出 #1

1

样例 #2

样例输入 #2

2
2 1
1 2

样例输出 #2

-1

样例 #3

样例输入 #3

4
1 2 3 4
5 6 7 8

样例输出 #3

0

样例 #4

样例输入 #4

5
28 15 22 43 31
20 22 43 33 32

样例输出 #4

-1

样例 #5

样例输入 #5

5
4 46 6 38 43
33 15 18 27 37

样例输出 #5

3

数据范围

• $1\ \leq\ N\ \leq\ 18$
• $1\ \leq\ A_i,\ B_i\ \leq\ 50$ ($1\ \leq\ i\ \leq\ N$)

样例解释 1

选择 $i\ =\ 1$ ，交换第 $1$ 张和第 $2$ 张卡片，此时面朝上的数字为 $[2,\ 3,\ 3]$ ，是单调不下降的。