AT_abc470_g [ABC470G] ΣШX

長さ $ 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 $ に含まれない最小の非負整数を表します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 以下の $ 6 $ 個の値の総和である $ 5 $ が答えです。 - $ \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 以下の $ 21 $ 個の値の総和である $ 31 $ が答えです。 - $ \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 $ - 入力される値はすべて整数