G - Alone Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

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

整数の組 (L, R) であって、以下の条件を満たすものの個数を求めてください。

  • 1 \leq L \leq R \leq N
  • A_L, A_{L + 1}, \ldots, A_R の中に 1 度だけ出現する数が存在する。より厳密には、ある整数 x が存在して、A_i = x かつ L \leq i \leq R を満たす整数 i の個数がちょうど 1 個である。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

5
2 2 1 2 1

出力例 1

12

(L, R) = (1, 1), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5) の 12 個の整数の組が条件を満たします。

入力例 2

4
4 4 4 4

出力例 2

4

入力例 3

10
1 2 1 4 3 3 3 2 2 4

出力例 3

47

Score: 575 points

Problem Statement

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

Find the number of pairs of integers (L, R) that satisfy the following conditions:

  • 1 \leq L \leq R \leq N
  • There is a number that appears exactly once among A_L, A_{L + 1}, \ldots, A_R. More precisely, there is an integer x such that exactly one integer i satisfies A_i = x and L \leq i \leq R.

Constraints

  • 2 \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 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5
2 2 1 2 1

Sample Output 1

12

12 pairs of integers satisfy the conditions: (L, R) = (1, 1), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5).

Sample Input 2

4
4 4 4 4

Sample Output 2

4

Sample Input 3

10
1 2 1 4 3 3 3 2 2 4

Sample Output 3

47