题目背景

实际上，我们的友情早已生锈、崩坏。

或许今天只是残骸上的碎片，恰巧散发出了微弱光芒而已。

即使如此......

题目描述

定义 $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$。

输出格式

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

4
0 0 1 2

4

7
3 1 0 1 2 2 0

3

10
1 1 0 0 2 2 3 3 0 0

10

提示

我仍然真的认为——那笑容非常灿烂，甚至令我指尖发麻。

对所有数据，满足 $1 \le n \le 3\times 10^6,0 \le a_i \le n$。

::cute-table{tuack}

特殊性质 A：$a_i=0$。

特殊性质 B：$0 \le a_i \le 10$。