题解

题面描述

给定一个数组，其元素均为 $0$ 或 $1$。定义一个数组的 $mex$ 为：该数组中没有出现过的最小非负整数。例如，数组 $[0,1,1,2,0,4]$ 的 $mex$ 是 $3$，数组 $[2,2,1]$ 的 $mex$ 是 $0$。
本题要求求出数组所有子数组（区间）的 $mex$ 之和。注意子数组个数为 $\frac{n(n+1)}{2}$。

思路

题目内容

定义一个数组的$mex$为：该数组没出现过的最小非负整数。例如,$[0,1,1,2,0,4]$的$mex$是$3,[2,2,1]$的$mex$是$0$。

现在小红拿到了一个数组，她希望你求出所有的区间$mex$之和。

请注意，共有$C(n+1,2)$个区间。

输入描述

第一行输入一个正整数$n$，代表数组的大小。

第二行输入$n$个非负整数$a$,代表数组的元素。

$1<n≤200000$

$0≤a_i≤1$

输出描述

所有的区间$mex$之和。

样例1

输入

3
1 1 0

输出

5

说明

区间$[3,3]$的$mex$是$1$

区间$[1,3]$和[2,3]的$mex$是$2$。

其余区间的$mex$是$0$。