题目描述

薯条哥拿到了一个数组，她希里你求出所有区间众数之和，你能帮帮她吗?

定义区间的众数为出现次数最多的那个数，如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数$n(1\le n\le 2\times 10^5)$，代表数组的大小

第二行输入$n$个正整数$a_i(1\le a_i\le 2)$,代表数组的元素

输出描述

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

样例

输入

3
2 1 2

输出

9

说明

[2],[2,1,2],[2]的众数是 2.
[2,1],[1],[1,2]的众数是 1.
因此答案是 9.