Alone

题目描述

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

输入格式

输入以标准输入的以下格式给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

5
2 2 1 2 1

12

4
4 4 4 4

4

10
1 2 1 4 3 3 3 2 2 4

47

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq N$ 所有输入值都是整数。$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)$.

标签: AtCoder|abc346G

来源

AtCoder|abc346G