AT_abc390_f [ABC390F] Double Sum 3

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。 对于满足 $1 \leq L \leq R \leq N$ 的整数对 $(L, R)$，定义 $f(L, R)$ 如下： - 初始时，在黑板上按顺序写下 $R-L+1$ 个整数 $A_L, A_{L+1}, \ldots, A_R$。 - 重复以下操作直到黑板上所有整数被清除： - 选择两个整数 $l, r$，需满足 $l \leq r$ 且黑板上当前存在的所有 $[l, r]$ 范围内的整数至少各出现一次。随后清除黑板上所有 $[l, r]$ 范围内的整数。 - $f(L, R)$ 定义为清除所有整数所需的最小操作次数。 请计算 $\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L, R)$ 的值。

输入从标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出答案。

### 约束条件 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq A_i \leq N$ - 输入的所有值均为整数 ### 样例解释 1 以 $(L, R) = (1, 4)$ 为例，计算 $f(L, R)$ 的过程如下： - 黑板上初始有 $1, 3, 1, 4$。 - 选择 $(l, r) = (1, 1)$，清除所有 $1$，此时黑板上剩余 $3, 4$。 - 选择 $(l, r) = (3, 4)$，清除 $3, 4$。 - 无法在少于 $2$ 次操作内完成清除，因此 $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$。 翻译由 DeepSeek R1 完成