103466: [Atcoder]ABC346 G - Alone

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

问题描述

给你一个整数序列$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$中有一个数恰好出现一次。更精确地说，存在一个整数$x$，使得恰好有一个整数$i$满足$A_i = x$和$L \leq i \leq R$。

约束

• $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

有$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)$。

样例输入2

4
4 4 4 4

样例输出2

4

样例输入3

10
1 2 1 4 3 3 3 2 2 4

样例输出3

47