分数: 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。更准确地说,有一个整数 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