Malnar 先生正在竞选 Tompojevci 县的县长。Tompojevci 县由一个村庄（名为 Tompojevci）组成，村庄里有一排 $n$ 栋房子，编号从 $1$ 到 $n$。每栋房子里住着一位居民，更重要的是，对于 Malnar 先生来说，他们每人都是一位选民。Malnar 先生知道，选举的胜负并不取决于谁是最好的候选人，而取决于谁能在选举前举办最好的宴会。因此，在选举前几天，他将举办一场宴会。他会邀请所有住在编号在 $l$ 到 $r$（包含 $l$ 和 $r$，$l \le r$）之间的房子里的居民，并为他们准备美味的餐点。

Malnar 先生非常了解 Tompojevci 的所有居民，因此他知道每位居民最喜欢的菜肴是什么。正因如此，他会为宴会准备一道菜，这道菜是受邀者中大多数人最喜欢的。然而，只有吃到自己最喜欢菜肴的人才会投票给 Malnar 先生，而其余的人会投票给唯一的另一位候选人 Vlado 先生。为了赢得选举，Malnar 先生需要获得投票总数中严格超过一半的选票。没有被邀请参加宴会的居民会忘记选举，因此不会投票。

Malnar 先生现在想知道，他有多少种不同的方式来选择数字 $l$ 和 $r$，以便他能赢得选举。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 200\,000$)。

第二行包含 $n$ 个正整数 $a_i$ ($1 \le a_i \le 10^9$)，分别代表住在第 $i$ 栋房子的居民最喜欢的菜肴。

输出格式

在唯一的一行中，输出 Malnar 先生选择 $l$ 和 $r$ 以赢得选举的不同方式的数量。

子任务

样例

样例输入 1

2
1 1

样例输出 1

3

样例输入 2

3
2 1 2

样例输出 2

4

样例输入 3

5
2 2 1 2 3

样例输出 3

10

说明

第二个样例的说明：可能的 $(l, r)$ 选择为：$(1, 1), (2, 2), (3, 3), (1, 3)$。