P3660 [USACO17FEB] Why Did the Cow Cross the Road III G

Farmer John 的农场布局非常独特，主田地的外围有一条环形道路，他的奶牛白天在这里吃草。每天早上，奶牛们都会穿过这条道路进入田地，每天晚上它们又会再次穿过这条道路离开田地返回牛棚。 众所周知，奶牛是习惯性动物，它们每天都会以相同的方式穿过道路。每头奶牛进入田地的点和离开田地的点不同，并且所有这些穿过点都彼此不同。Farmer John 拥有 $N$ 头奶牛，方便地用整数 ID $1 \ldots N$ 标识，因此道路周围恰好有 $2N$ 个穿过点。Farmer John 通过顺时针扫描环形道路，记录每个穿过点的奶牛 ID，最终形成一个包含 $2N$ 个数字的序列，其中每个数字恰好出现两次。他并未记录哪些穿过点是进入点，哪些是离开点。 看着他的穿过点地图，Farmer John 好奇一天中不同奶牛对之间可能会交叉多少次。如果奶牛 $a$ 从进入点到离开点的路径必须与奶牛 $b$ 从进入点到离开点的路径交叉，那么他称奶牛对 $(a,b)$ 为“交叉”对。请帮助 Farmer John 计算交叉对的总数。

无

无