P3656 [USACO17FEB] Why Did the Cow Cross the Road I P

为什么奶牛要过马路？我们可能永远无法知道完整的原因，但可以肯定的是，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$ 的任何过马路路径相交。 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。请确定在对马路一侧的田地进行适当的循环移位后，可能存在的交叉品种对的最小数量。

无

无