题目思路

​ 对于这题，我们可以将1视为 -1，2 视为 1，那么区间 $[l, r]$ 的和就相当于区间中 2 的数量减去 1 的数量，如果该区间的和 > 0，则说明对于区间 $[l, r]$ 而言，区间的众数为 2 ，否则为 1 。

​ 为了区间和的计算方便，这里采用前缀和来进行处理:

• 记 $s[i]$ 为前 $i$ 个数的和，那么区间 $[l, r]$ 的和可以表示为: $s[r] - s[l - 1]$

​ 将本题转换为，对于每个位置 $r$，找到其左侧所有满足 $s[r] - s[l] > 0，l \in [1, r - 1]$ 的数量

题目描述

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

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

输入描述

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

第二行输入$n$个正整数$a_i$,代表数组的元素

$1\le n\le 2\times 10^5$

$1\le a_i\le 2$

输出描述

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

样例

输入

3
2 1 2

输出

9

说明

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