E - I Hate Sigma Problems Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。また、f(l,r) を以下で定義します。

  • (A_l,A_{l+1},\ldots,A_{r-1},A_{r}) に含まれる値の種類数

次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j)


制約

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

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
1 2 2

出力例 1

8

f(1,2) について考えます。(A_1,A_2)=(1,2) に含まれる値の種類数は 2 なので f(1,2)=2 です。

f(2,3) について考えます。(A_2,A_3)=(2,2) に含まれる値の種類数は 1 なので f(2,3)=1 です。

f の総和は 8 となります。

入力例 2

9
5 4 2 2 3 2 4 4 1

出力例 2

111

Score : 475 points

Problem Statement

You are given a sequence of integers A = (A_1, A_2, \ldots, A_N) of length N. Define f(l, r) as:

  • the number of distinct values in the subsequence (A_l, A_{l+1}, \ldots, A_r).

Evaluate the following expression:

\displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j).


Constraints

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

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

3
1 2 2

Sample Output 1

8

Consider f(1,2). The subsequence (A_1, A_2) = (1,2) contains 2 distinct values, so f(1,2)=2.

Consider f(2,3). The subsequence (A_2, A_3) = (2,2) contains 1 distinct value, so f(2,3)=1.

The sum of f is 8.

Sample Input 2

9
5 4 2 2 3 2 4 4 1

Sample Output 2

111