102523: [AtCoder]ABC252 D - Distinct Trio
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $400$ points
Problem Statement
You are given a sequence of length $N$: $A=(A_1,A_2,\ldots,A_N)$.
Find the number of triples $(i,j,k)$ that satisfy both of the following conditions.
- $1\leq i \lt j \lt k \leq N$
- $A_i$, $A_j$, and $A_k$ are distinct.
Constraints
- $3 \leq N \leq 2\times 10^5$
- $1 \leq A_i \leq 2\times 10^5$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 3 1 4 1
Sample Output 1
2
The two triples $(i,j,k)$ satisfying the conditions are $(1,2,3)$ and $(1,3,4)$.
Sample Input 2
10 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990
Sample Output 2
120
Sample Input 3
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Sample Output 3
355
Input
题意翻译
有一个长度为 $n$ 的数列 $A$，求满足以下条件的三元组的数量： * $1 \leq i < j < k \leq n $ * $A_i$，$A_j$，$A_k$ 互不相同 $ 3 \leq n \leq 2 \times 10^5 $ $ 1 \leq A_i \leq 2 \times 10^5 $Output
得分：400分
部分
问题描述
给定一个长度为 N 的序列 A=(A1,A2,…,AN)。
找到满足以下两个条件的三元组 (i,j,k) 的数量。
1≤i＜j＜k≤N
Ai，Aj 和 Ak 是不同的。
部分
约束
3≤N≤2×105
1≤Ai≤2×105
输入中的所有值都是整数。
部分
输入
输入以以下格式从标准输入给出：
N
A1 A2 … AN
部分
输出
打印答案。
部分
样例输入 1
4
3 1 4 1
部分
样例输出 1
2
满足条件的两个三元组 (i,j,k) 是 (1,2,3) 和 (1,3,4)。
部分
样例输入 2
10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990
部分
样例输出 2
120
部分
样例输入 3
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
部分
样例输出 3
355