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

加入题单

上一题 下一题 算法标签: