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$

输出答案。

### 样例解释 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$ - 所有输入均为整数。 由 ChatGPT 5 翻译