互不相同的三元组

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。

求同时满足以下两个条件的三元组 $(i, j, k)$ 的个数。

• $1 \le i \lt j \lt k \le N$
• $A_i$、$A_j$ 和 $A_k$ 互不相同。

输入格式

输入按以下格式从标准输入给出：

N
A_1 A_2 … A_N

输出格式

打印答案。

样例

4
3 1 4 1

2

满足条件的三元组 $(i, j, k)$ 为 $(1, 2, 3)$ 和 $(1, 3, 4)$ 两个。

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

120

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

355

数据范围

• $3 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$
• 输入中的所有值均为整数。