AT_abc470_g.Σex

You are given a length-$N$ sequence of non-negative integers $A = (A_1, \dots, A_N)$.

Find the sum of $\mathrm{mex}({A_l, \cdots, A_r})$ over all pairs of integers $(l, r)$ satisfying $1 \leq l \leq r \leq N$.

Here, $\mathrm{mex}({A_l, \cdots, A_r})$ denotes the smallest non-negative integer not contained in $A_l, \cdots, A_r$.

给你一个长度为 $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$ 中出现的最小非负整数。

The input is given from Standard Input in the following format:

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

输入从标准输入中按以下格式给出：

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

Output the answer.

输出答案。

Sample 1 Explanation:
The answer is $5$, the sum of the following $6$ values.

• $\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$

Sample 2 Explanation:
The answer is $31$, the sum of the following $21$ values.

• $\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$

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq A_i \leq N$
• All input values are integers.

样例 1 解释：
答案为 $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 解释：
答案为 $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$

约束条件

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