学生爱丽丝和易卜拉欣是最好的朋友。马上就要到易卜拉欣的生日了,所以爱丽丝决定送给他一个新拼图。该谜题可以表示为一个具有 $$$2$$$ 行和 $$$n$$$ 列的矩阵,其中每个元素都是 $$$0$$$ 或 $$$1$$$。一步操作中,您可以交换相邻单元格中的两个值。
更正式地说,让我们从上到下对行 $$$1$$$ 到 $$$2$$$ 进行编号,从左到右对 $$$1$$$ 到 $$$n$$$ 列进行编号。另外,我们将 $$$x$$$ 行和 $$$y$$$ 列中的单元格表示为 $$$(x, y)$$$。如果 $$$|x_1 - x_2|,我们认为单元格 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 相邻+ |y_1 - y_2| = 1$$$。
Alice 不喜欢当前单元格的排列方式,因此她想出了自己的排列方式,她想将拼图赠送给 Ibragim。由于你是她最聪明的朋友,她要求你帮助她找到尽可能少的操作次数,以便她能够得到想要的安排。找到这个号码,或者确定不可能得到新的安排。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — 拼图中的列数。
以下两行描述了拼图上当前的排列。每一行包含 $$$n$$$ 个整数,每个整数要么是 $$$0$$$ 要么是 $$$1$$$。
最后两行以相同的格式描述了 Alice 所需的排列。
输出
如果可以获得所需的排列,则打印尽可能少的步骤数,否则打印 $$$-1$$$。
示例
输入 #1
5 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0
输出 #1
5
输入 #2
3 1 0 0 0 0 0 0 0 0 0 0 0
输出 #2
-1
注意
在第一个示例中,以下交换序列就足够了:
- $$$(2, 1), (1, 1)$$$,
- $$$(1, 2), (1, 3)$$$,
- $$$(2, 2), (2, 3)$$$,
- $$$(1, 4), (1, 5)$$$,
- $$$(2, 5), (2, 4)$$$.
可以证明,$$$5$$$ 是这种情况下的最小可能答案。
在第二个示例中,无论您进行什么交换,都不会得到所需的排列,因此答案是 $$$-1$$$。