You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$N$ 个数字对（称为“情侣对”）排成一列。

给定一个长度为 $2N$ 的序列 $A = (A_1, A_2, \dots, A_{2N})$，其中每个 $1, 2, \dots, N$ 恰好出现两次。

请统计满足以下所有条件的 两对不同的情侣对 $(a, b)$ 的组数：

$1$. 在原序列中，$a$ 的两个出现位置不相邻。

$2$. 在原序列中，$b$ 的两个出现位置不相邻。

$3$. 通过执行以下操作（次数不限），可以使 $a$ 的两个出现位置邻接，同时 $b$ 的两个出现位置也邻接：

• 选择两个位置 $(i, j)$ 满足 $A_i = a$ 且 $A_j = b$，并交换这两个位置的值。

形式化的理解：给你 $2 \times n$ 个数，$[1,n]$ 里每个数都出现两次，求有多少对 $（a,b）$ ，使得序列里 $a$ 出现的两个位置都不相邻和 $b$ 出现的两个位置都不相邻然后交换它们某两个位置上的数可以使得两个数的两个出现的位置都相邻。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_{2N}$

输出格式

输出答案。

样例 #1

输入 #1

3
1 2 3 3 1 2

输出 #1

1

样例 #2

输入 #2

5
1 2 3 4 5 1 2 3 4 5

输出 #2

4

说明/提示

样例解释 1

考虑第一个测试用例 $(a, b) = (1, 2)$：

原序列中 $1$ 的两个出现位置不相邻。 原序列中 $2$ 的两个出现位置不相邻。

选择 $(i, j) = (1, 6)$ 交换 $A_1$ 和 $A_6$ 后:

$1$ 的两个位置相邻 $2$ 的两个位置相邻。

因此满足条件的二元组 $(a, b)$ 仅有 $(1, 2)$ 这一组。

约束条件

对于$40\%$的样例：保证 $1 \leq N \leq 2 \times 1000$

对于$100\%$的样例：保证 $1 \leq N \leq 2 \times 10^5$ ， $1 \leq A_i \leq N$ ， 每个 $1, 2, \dots, N$ 在 $A$ 中恰好出现两次 ，输入值均为整数

• 时间限制: $2s$
• 空间限制: $256 MB$