P14203 这次要永远 做朋友

实际上，我们的友情早已生锈、崩坏。 或许今天只是残骸上的碎片，恰巧散发出了微弱光芒而已。 即使如此......

定义 $f(l,r)$ 为 $\{a_l,a_{l+1},\dots,a_r\}$ 的绝对众数的值。若不存在，则 $f(l,r)=10^{100}$。也就是出现次数 $c > \lfloor\frac{r-l+1}{2}\rfloor$ 的值。 定义 $\operatorname{mex}(l,r)$ 为 $\{a_l,a_{l+1},\dots,a_r\}$ 的 $\operatorname{mex}$ 值。也就是最小的不存在的自然数。 给定长度为 $n$ 的序列 $a_{1\dots n}$，求 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[\operatorname{mex}(l,r)\ge f(l,r)]$。

第一行一个整数 $n$。 第二行 $n$ 个整数 $a_i$。

一行一个整数，表示答案。

我仍然真的认为——那笑容非常灿烂，甚至令我指尖发麻。 对所有数据，满足 $1 \le n \le 3\times 10^6,0 \le a_i \le n$。 ::cute-table{tuack} |子任务编号|$n\le$|特殊性质|分值|时间限制| |:-:|:-:|:-:|:-:|:-:| |#1|$100$|无|$\text{5pts}$|$\text{1s}$| |#2|$5000$|^|$\text{5pts}$|^| |#3|$3 \times 10^4$|^|$\text{15pts}$|^| |#4|$10^5$|^|$\text{15pts}$|^| |#5|^|B|$\text{10pts}$|^| |#6|$3\times 10^6$|A|$\text{2pts}$|^| |#7|^|无|$\text{24pts}$|^| |#8|^|无|$\text{24pts}$|$\text{450ms}$| 特殊性质 A：$a_i=0$。 特殊性质 B：$0 \le a_i \le 10$。