Why Did the Cow Cross the Road

题目描述

奶牛为什么要过马路？我们也许永远无法知道完整原因，但可以确定的是，Farmer John 的奶牛确实经常要过马路。事实上，她们过马路的次数太多，以至于当路径相交时经常彼此撞到，这种情况 Farmer John 希望能够避免。

Farmer John 饲养了 $N$ 个品种的奶牛（$1 \leq N \leq 100,000$），并且他的每块牧场田地都专门用于某一个特定品种的放牧；例如，一块分配给品种 12 的田地只能用于品种 12 的奶牛，不能用于其他任何品种。

一条长路穿过他的农场。路的一侧有一列共 $N$ 块田地（每个品种一块），路的另一侧也有一列共 $N$ 块田地（同样每个品种一块）。因此，当一头奶牛过马路时，她会在属于她自己品种的两块田地之间穿行。

如果 Farmer John 规划得更周到，他会让马路两侧的田地按品种编号以相同顺序排列，这样每个品种对应的两块田地就会正对着彼此。这样就能让奶牛过马路时，不同品种的奶牛不会互相碰撞。可惜，马路两侧的排列顺序可能不同，因此 Farmer John 观察到可能会存在一些“相交”的品种对。

对于不同的两个品种 $(a,b)$，如果品种 $a$ 的任意一条过马路路径都必须与品种 $b$ 的任意一条过马路路径相交，那么称这对品种 $(a,b)$ 是“相交”的。

Farmer John 希望将相交的品种对数量最小化。出于后勤原因，他认为可以在马路的一侧移动奶牛，使该侧的田地顺序发生一次“循环平移”。也就是说，对于某个 $0 \leq k < N$，每头奶牛都搬到前方第 $k$ 块田地中，而原本最后 $k$ 块田地中的奶牛将移动到最前面的 $k$ 块田地中。例如，如果马路一侧的田地按品种顺序为 3, 7, 1, 2, 5, 4, 6，并进行 $k=2$ 的循环平移，那么新顺序将变为 4, 6, 3, 7, 1, 2, 5。

请确定：在对马路一侧的田地进行适当的循环平移后，可能存在的相交品种对的最小数量。

输入格式

第一行输入 $N$。 接下来 $N$ 行按品种编号描述马路一侧田地的顺序；每个品种编号是范围 $1 \ldots N$ 内的整数。 最后 $N$ 行按品种编号描述马路另一侧田地的顺序。

输出格式

请输出在对马路一侧的田地进行一次循环平移之后（两侧任意一侧都可以平移），相交的品种对的最小数量。

5
5
4
1
3
2
1
3
2
5
4

0

提示

题目致谢：Brian Dean

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum