题目描述

译自 COCI 2021/2022 Contest #4 T3「Izbori」

Manlar 先生正在竞选 Tompojevci 县的县长。Tompojevci 县由一个（叫 Tompojevci 的）村组成，这个村由一排 $n$ 座房子组成，房子从 $1$ 到 $n$ 编号。每个房子中住着一位居民，但是对于 Manlar 先生更重要的是，他们都是选民。Malnar 先生知道选举中获胜的人不是最好的竞选者，而是在选举前举行的宴会最好的竞选者。因此，在选举前几天他会组织一次宴会。他会邀请住在编号从 $l$ 到 $r$（$l\le r$，包括两端）的房子中所有的居民，并且为他们准备一顿美味的午餐。

Manlar 十分了解所有 Tompojevci 的居民，因此他知道每位居民最喜欢吃什么菜。这就是为什么他会准备被邀请的人中喜欢的菜最多的那种。然而，只有吃到他最喜欢的菜的人才会给 Malnar 先生投票，其余的人会给唯一的另一位候选者 Vlado 先生投票。为了赢得选举，Malnar 先生需要获得严格大于一半的票数。没有被邀请到聚会的选民会忘掉选举，并且不会参与投票。

Malnar 先生现在想知道有多少种不同的方式去选择 $l$ 和 $r$ 的值，才能让他赢得选举。

输入格式

第一行包含一个正整数 $n$，意义如题目描述。

第二行包含 $n$ 个正整数 $a_i$，第 $i$ 个整数表示住在房子 $i$ 中的居民最喜欢的菜。

输出格式

输出一行一个整数，表示 Malnar 先生想要赢得选举的情况下选择 $l$ 和 $r$ 的方案数。

2
1 1

3

3
2 1 2

4

5
2 2 1 2 3

10

数据范围与提示

对于全部数据，$1\le n\le 2\times 10^5,1\le a_i\le 10^9$。

详细子任务附加限制及分值如下表所示：