问题陈述

给你一个长度为 $N$ 的非负整数序列 $A = (A_1, \dots, A_N)$ 。

求所有满足 $1 \leq l \leq r \leq N$ 的整数对 $(l, r)$ 中 $\mathrm{mex}({A_l, \cdots, A_r})$ 的和。

这里， $\mathrm{mex}({A_l, \cdots, A_r})$ 表示不包含在 $A_l, \cdots, A_r$ 中的最小非负整数。

约束条件

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq A_i \leq N$
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出

输出答案

输入示例 1

3
1 2 0

样本输出 1

5

答案是 $5$ ，即下列 $6$ 值的总和。

• $\mathrm{mex}({A_1}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_1,A_2}) = \mathrm{mex}({1,2}) = 0$
• $\mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({1,2,0}) = 3$
• $\mathrm{mex}({A_2}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_2,A_3}) = \mathrm{mex}({2,0}) = 1$
• $\mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1$

输入样本 2

6
2 1 0 2 1 4

样本输出 2

31

答案是 $31$ ，即下列 $21$ 值的总和。

• $\mathrm{mex}({A_1}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_1,A_2}) = \mathrm{mex}({2,1}) = 0$
• $\mathrm{mex}({A_1,A_2,A_3}) = \mathrm{mex}({2,1,0}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4}) = \mathrm{mex}({2,1,0,2}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4,A_5}) = \mathrm{mex}({2,1,0,2,1}) = 3$
• $\mathrm{mex}({A_1,A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({2,1,0,2,1,4}) = 3$
• $\mathrm{mex}({A_2}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_2,A_3}) = \mathrm{mex}({1,0}) = 2$
• $\mathrm{mex}({A_2,A_3,A_4}) = \mathrm{mex}({1,0,2}) = 3$
• $\mathrm{mex}({A_2,A_3,A_4,A_5}) = \mathrm{mex}({1,0,2,1}) = 3$
• $\mathrm{mex}({A_2,A_3,A_4,A_5,A_6}) = \mathrm{mex}({1,0,2,1,4}) = 3$
• $\mathrm{mex}({A_3}) = \mathrm{mex}({0}) = 1$
• $\mathrm{mex}({A_3,A_4}) = \mathrm{mex}({0,2}) = 1$
• $\mathrm{mex}({A_3,A_4,A_5}) = \mathrm{mex}({0,2,1}) = 3$
• $\mathrm{mex}({A_3,A_4,A_5,A_6}) = \mathrm{mex}({0,2,1,4}) = 3$
• $\mathrm{mex}({A_4}) = \mathrm{mex}({2}) = 0$
• $\mathrm{mex}({A_4,A_5}) = \mathrm{mex}({2,1}) = 0$
• $\mathrm{mex}({A_4,A_5,A_6}) = \mathrm{mex}({2,1,4}) = 0$
• $\mathrm{mex}({A_5}) = \mathrm{mex}({1}) = 0$
• $\mathrm{mex}({A_5,A_6}) = \mathrm{mex}({1,4}) = 0$
• $\mathrm{mex}({A_6}) = \mathrm{mex}({4}) = 0$

输入样本 3

25
2 2 1 2 2 0 2 2 2 1 2 2 2 0 2 2 2 2 1 2 2 2 2 0 2

输出样本 3

624