AT_abc470_g [ABC470G] ΣШX

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

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

Output the answer.

### Sample Explanation 1 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 Explanation 2 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.