第 4 题 Izbori (izbori)

时间限制 1.0 s · 空间限制 256 MB · 54 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 izbori.in，输出文件 izbori.out。

题目描述

Malnar 先生正在竞选县长，这个县一共有 $n$ 栋房屋，每栋房屋里都住着一位居民。Malnar 先生知道，选举的赢家不一定是最好的候选人，而是在选举前举办的宴会最好的候选人。因此，在选举前几天，他将邀请第 $l$ 至 $r$($l \le r$) 栋房屋内居住的居民，为他们准备一顿丰盛的晚餐。

Malnar 先生知道所有居民最喜欢吃的菜。在宴会上，他会准备大多数人喜欢的一道菜。如果一个人吃到了自己最喜欢吃的菜，将会投一票给 Malnar 先生。但是如果没有吃到自己最喜欢吃的菜，他们将会把票投给 Vlado 先生。如果没有来参加晚宴的居民，他们将会忘记选举，不做出任何投票。如果一个候选人获得了投了票的人中一半以上的人的支持，他将会赢得竞选。

Malnar 先生想知道，有多少组的 $(l, r)$ 可以使他赢得竞选。

输入格式

第一行包含一个整数 $n$，表示房屋的数量。

第二行包含 $n$ 个整数 $a_i$，表示第 $i$ 栋房屋内居民最喜欢的菜。

输出格式

仅一行，输出可以使 Malnar 先生赢得竞选的 $(l, r)$ 的组数。

样例

样例 1

输入：

2
1 1

输出：

3

样例 2

输入：

3
2 1 2

输出：

4

样例 3

输入：

5
2 2 1 2 3

输出：

10

提示

【样例 2 解释】

可以使 Malnar 先生赢得竞选的 $(l, r)$ 为：$(1, 1), (2, 2), (3, 3), (1, 3)$。

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1 (10 pts) ：$1 \le n \le 300$。
• Subtask 2 (15 pts) ：$1 \le n \le 2 \times 10^3$。
• Subtask 3 (15 pts) ：$\forall i \in 1, 2, 3, \ldots, n, 1 \le a_i \le 2$。
• Subtask 4 (70 pts) ：没有额外限制。

对于 100% 的数据，$1 \le l \le r \le n \le 2 \times 10^5, 1 \le a_i \le 10^9$。

【提示与说明】

**

**