H - Sandwich triplet Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

整数 N と長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

以下の条件を全て満たす整数の組 (i,j,k) を サンドイッチな組 と呼びます。

  • 1\le i < j < k \le N
  • A_i=A_k\neq A_j

サンドイッチな組がいくつあるか求めてください。

制約

  • 3\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

5
2 5 2 2 5

出力例 1

4

(i,j,k)=(1,2,3),(1,2,4),(2,3,5),(2,4,5) がサンドイッチな組です。

入力例 2

5
4 4 4 4 4

出力例 2

0

どのように (i,j,k) を選んでも A_i=A_k\neq A_j を満たしません。

入力例 3

10
2 2 6 4 4 6 6 2 3 2

出力例 3

27

Problem Statement

You are given an integer N, and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

A sandwich triple is an integer triple (i,j,k) such that:

  • 1\le i < j < k \le N; and
  • A_i=A_k\neq A_j.

How many sandwich triples are there?

Constraints

  • 3\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • All input values are integers.

Input

The 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

5
2 5 2 2 5

Sample Output 1

4

The sandwich triples are (i,j,k)=(1,2,3),(1,2,4),(2,3,5),(2,4,5).

Sample Input 2

5
4 4 4 4 4

Sample Output 2

0

No choice of (i,j,k) satisfies A_i=A_k\neq A_j.

Sample Input 3

10
2 2 6 4 4 6 6 2 3 2

Sample Output 3

27