G - ΣШX

Problem Statement

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$.

Constraints

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

Input

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

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

Output

Output the answer.

3
1 2 0

5

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$

6
2 1 0 2 1 4

31

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$

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

624

• 来源：AtCoder ABC 470 G