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 完成