← 返回题目列表

AtCoder · kupc2015_g

G. 剑道

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

問題文

京都市流行一种名为剑道的运动。

什么是剑道?N 这是一项由两队人相互竞争的运动。 参加剑道的人都有一个整数值,称为“Wazamae”。

剑道执行如下。

  • 首先,各队决定顺序,排成一排。
  • 接下来,N 一木内按顺序执行。
  • i ( 1 \leq i \leq N ) 第二次是 每个团队的 这是在排队的第 i 个人之间完成的。
  • 一木内,一个有着波座前的小人物 科吉梅 如果对手的牌数相同,则为平局,双方都将 科吉梅 未完成。

高桥队即将与青木队进行剑道比赛。 高桥小队的顺序已经决定了。 由于之前的间谍活动,青木的队伍是按照难度从高到低的顺序排列的。 我也获得了诀窍的价值。 于是,高桥改变了队伍的顺序, 无论您身在何处,您的团队成员 科吉梅 我想防止这种情况发生。

由于各种情况,队伍的顺序可能会有所不同。 相邻 这只能通过选择两个人并交换他们的订单来完成。 由于距比赛时间已所剩无几,您可以以尽可能少的交换次数交换队伍中的任何成员。 科吉梅 我想重新安排它,以免发生这种情况。 因此,我希望您计算并输出交换次数。 然而,无论你如何交流,你的一名团队成员都会 科吉梅 如果发生 -1 。

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
  • 1 行是一个整数 给出 N ( 1 \leq N \leq 10^5 )。
  • 2 在线 N 整数 给出 A_i ( 1 \leq i \leq N ) 用空格分隔。A_i ( 0 \leq A_i \leq 10^9 ) 来自 Takahashi 的团队。 代表第 i 个人的技能。
  • 3 在线 N 整数 给出 B_i ( 1 \leq i \leq N ) 用空格分隔。B_i ( 0 \leq B_i \leq 10^9 ) 来自 Aoki 的团队。 i 个人的技能。
  • B_i \leq B_{i+1} ( 1 \leq i \leq N-1 )成立。

出力

计算满足条件所需的最小交换次数。 输出为 1 行。 但如果无论如何交换都无法满足条件 -1 。

部分点

如果满足以下约束的数据集的所有答案都是正确的, 3 给出了点的部分点。

  • N \leq 10^3


入力例1

3
6 2 4
1 3 5

出力例1

2

首先,Udemae。 2 人和 Udemae 替换 6 人, 接下来是乌德前 替换 6 人和 Udemae 替换 4 中的人。 此时Udemae的顺序是 2, 4, 6 和任何成员 科吉梅 将不再使用。


入力例2

3
7 2 6
1 3 5

出力例2

1

乌德前 2 人和 Udemae 替换 7 中的人。 此时Udemae的顺序是 2, 7, 6 和任何成员 科吉梅 将不再使用。


入力例3

3
8 8 8
2 7 9

出力例3

-1

无论你如何重新排列顺序,最后一个对手 科吉梅 有