题解

题目描述

给定一个由$n$个整数构成的数组$\{a_1,a_2,\dots,a_n\}$，其中每个$a_i$满足$0\le a_i\le 2$。定义一个数组的$mex$为未出现在该数组中的最小非负整数。例如

• $mex\{1,2,3\}=0$
• $mex\{0,2,5\}=1$

要求取出数组中的所有连续非空子数组，并求每个子数组的$mex$值之和。
连续非空子数组指从原数组中取出一段连续的元素（可以取全数组，也可以取部分），且该子数组至少包含一个元素。

题目内容

整数数组的$mex$定义为没有出现在数组中的最小非负整数。例如$mex(1,2,3)=0,mex(0,2,5)=1$。 现在，对于给定的由$n$个整数组成的数组{$a_1,a_2,...,a_n$}，取出全部连续非空子数组，并计算每个子数组的$mex$之和。

连续非空子数组为从原数组中，连续的选择一段元素(可以全选、可以不选)得到的新数组，且新数组中至少有一个元素。

输入描述

第一行输入一个整数$n(1<=n<=2×10^5)$代表数组中的元素数量。

第二行输入$n$个整数$a_1,a_2,...,a_n (0<=a_i<=2)$代表数组元素。

输出描述

输出一个整数，代表所有子数组的$mex$之和。

样例1

输入

3
1 1 0

输出

3

说明

在这个样例中，答案由以下三部分构成:

长度为$1$的连续子数组:$(1)$。$(1)、(0)$，$mex$之和为$0+0+1=1$

长度为$2$的连续子数组:$(1,1)、(1,0)，mex$之和为$0+2=2$

长度为的固挂子数据:$(1,1,0)$，$mex$之和为$2$。

因此，答案为$1+2+2=5$。