You are given an array of $N$ positive integers $a_1,a_2,\dots ,a_N$. Find the number of subarrays that have a majority element.

A subarray of length $l$ has a majority element if some number appears strictly greater than $\frac{1}{2}l$ times in the subarray.

Constraints

$1\le a_i\le N$ for all $i$.

Subtask 1 [5%]

$1\le N\le 100$

Subtask 2 [10%]

$1\le N\le 500$

Subtask 3 [15%]

$1\le N\le 2000$

Subtask 4 [20%]

$1\le N\le 10000$

Subtask 5 [25%]

$1\le N\le 100000$

Subtask 6 [25%]

$1\le N\le 2000000$

Input Specification

The first line of input contains one integer: $N$.

The second line of input contains $N$ space-separated integers. The $i$th of these integers is $a_i$.

Output Specification

Output one number: the number of subarrays that have a majority element.

Sample Input 1

4
1 2 1 3

Sample Output 1

5

Explanation for Sample Output 1

All $4$ single-element subarrays have a majority element, and the subarray $[1,2,1]$ also has a majority element.

Sample Input 2

10
1 3 2 3 1 3 3 2 2 4

Sample Output 2

25