seuOJ9164 - 猪计数

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：Div.2, 2025 帆软杯

题目描述

有一天，上帝给了猪 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

猪闲得无聊，想从这些数中选三个偷偷带回宿舍。

为了好看，猪要求其中两个数相等，剩下的一个数与它们不相等。

形式化地，猪想选一个整数三元组 $(i,j,k)$ 满足 $1\le i<j<k\le n$ 且 $\big|\big\{a_x\mid x\in\{i,j,k\}\big\}\big|=2$。

上帝认为这太简单，于是问猪：有多少个整数三元组 $(i,j,k)$ 满足上述要求？

猪不会这个问题，于是便顺其自然地把它甩给了你。

不过，猪倒是担心答案可能比较大，请你帮他想想办法。

输入格式

第一行一个整数 $n$（$3\le n\le2\times10^5$）。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1\le a_i\le n$）。

输出格式

一行一个整数，表示满足要求的三元组的数量。

样例

样例 1

输入

5
3 2 5 2 2

输出

6

解释

满足要求的三元组有 $(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5)$。

样例 2

输入

3
1 1 1

输出

0

解释

很遗憾，没有满足要求的三元组。