题目描述

小张拿到了一个数组。他希望你求出所有区间众数之和。你能帮帮他吗？定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入格式

第一行输入一个正整数n，代表数组的大小。 第二行输入n个正整ai，代表数组的元素。 1<=n<=200000 1<=ai<=2

输出格式

一个正整数，代表所有区间的众数之和。

输入数据1

3
2 1 2

输出数据

9

提示

解释样例：

众数是2的区间为：2 ,2 1 2, 2,三个众数是2的区间 2*3 =6

众数是1的区间为：2 1，1，1 2， 三个众数是1的区间 3*1=3 结果为：6+3 =9