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 2\,000~

Subtask 4 [20%]

~1 \le N \le 10\,000~

Subtask 5 [25%]

~1 \le N \le 100\,000~

Subtask 6 [25%]

~1 \le N \le 2\,000\,000~

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