分数: 525 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
对于每个整数对 (L,R) 与 1 \le L \le R \le N,定义 f(L,R) 如下:
- 从一块空黑板开始。写下 黑板上按顺序 R-L+1 整数 A_L, A_{L+1}, \ldots, A_R 。
- 重复以下操作,直到黑板上的所有整数都被擦除:
- 选择整数 l, r 与 l \le r 这样每个整数 l 通过 r 在黑板上至少出现一次。然后,删除所有整数 黑板上的 l 通过 r 。
- 让 f(L,R) 是从黑板上擦除所有整数所需的此类操作的最少数量。
查找 \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).
约束
- 1 \le N \le 3 \times 10^5
- 1 \le A_i \le N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
4 1 3 1 4
示例输出 1
16
例如,在以下情况 (L,R)=(1,4):
- 黑板上有 1,3,1,4.
- 选择 (l,r)=(1,1) 并删除所有出现的 1。现在黑板上有 3,4.
- 选择 (l,r)=(3,4) 并删除所有出现的 3 和 4。黑板变成空的。
- 它不能通过少于两次操作完成,所以 f(1,4) = 2.
同样,你可以找到 f(2,4)=2, f(1,1)=1等
\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16,所以打印 16.
示例输入 2
5 3 1 4 2 4
示例输出 2
23
示例输入 3
10 5 1 10 9 2 5 6 9 1 6
示例输出 3
129