Score: $575$ points

问题陈述

给定一个整数序列 $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$。

以上为大语言模型 kimi 翻译，仅供参考。

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

update @ 2024/5/16 17:18:29