题目内容

对于一个整数集合，定义它的「缺省数」为未出现在该集合中的最小非负整数。例如，集合 $\{1,2,3\}$ 的缺省数为 $0$，集合 $\{0,2,5\}$ 的缺省数为 $1$。

现在给定一个长度为 $n$ 的整数序列 $x_1, x_2, \dots, x_n$，序列中的每个元素只可能是 $0$、$1$ 或 $2$。考虑该序列的所有非空连续子段，求每个子段的缺省数之和。

序列的长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，且每个 $x_i$ 均为 $0$、$1$ 或 $2$。

输入描述

第一行包含一个整数 $n$。 第二行包含 $n$ 个整数，依次表示序列元素 $x_1, x_2, \dots, x_n$，每个整数均为 $0$、$1$ 或 $2$。