E - MCC Sequence (Calculate Version)
Benihuki
2
s
1024
MB
200
点
問題文
長さ $n$ の数列 $a = (a_1, \dots, a_n)$ に対し、$f(a)$ を次の条件をすべて満たす整数 $(i, j, k)$ の組の個数と定義します。この定義はF問題と同じです。
- $1 \le i < j < k \le n$
- $a_i \ne a_j$
- $a_i \ne a_k$
- $a_j = a_k$
長さ $N$ の数列 $A = (A_1, \dots, A_N)$ が与えられます。$f(A)$ の値を求めてください。
制約
Hard (75点)
- $3 \le N \le 2 \times 10^5$
- $1 \le A_i \le N$
- 入力はすべて整数
Normal (50点)
- Hard の制約に以下の制約を追加
- $3 \le N \le 1000$
Easy (75点)
- Hard の制約に以下の制約を追加
- $3 \le N \le 100$
部分点のみ解答したい場合
部分点のみを解答したい場合、問題によっては結果が TLE となるケースが大量に発生し、ジャッジに時間がかかる可能性があります。
C++の assert 関数やPythonの assert 文などを用いて、変数の値によってプログラムを強制終了させる処理を書き加えることで TLE を防ぎ、より早く結果を得ることができます。
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1 \ \ \dots \ \ A_N$
出力
答えを $1$ 行に出力してください。
入力例 1
5
1 2 2 3 3
出力例 1
4
条件を満たす $(i, j, k)$ の組は次の $4$ つです。
- $(1, 2, 3)$
- $(1, 4, 5)$
- $(2, 4, 5)$
- $(3, 4, 5)$
よって、$f(A) = 4$ より、$4$ を出力してください。
この入出力例は Easy・Normal・Hard の制約を満たします。
入力例 2
9
9 9 8 2 4 4 3 5 3
出力例 2
10
この入出力例は Easy・Normal・Hard の制約を満たします。