题目描述

整数数组的$mex$定义为没有出现在数组中的最小非负整数。

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

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

输入描述

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

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

输出描述

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

样例

输入

3
1 1 0

输出

3

样例解释

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

长度为$1$的连续子数组:$[1],[1],[0]$，$mex$之和为$0+0+1=1$

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

长度为的$3$子数据:$[1,1,0]$，$mex$之和为$2$。

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