Một dãy số hữu hạn được gọi là có phần tử áp đảo số lượng nếu tồn tại một phần tử có số lần xuất hiện nhiều hơn một nửa số lượng phần tử của dãy.

Yêu cầu: Cho số nguyên dương ~n~ và dãy số nguyên ~a_1,a_2,\dots,a_n~, hãy đếm số cặp số nguyên ~(l,r)~ thỏa mãn ~1 \le l \le r \le n~ và dãy ~a_l,a_{l+1},a_{l+2},\dots,a_r~ có phần tử áp đảo số lượng.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~;

• Dòng thứ 2 chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9, \forall i=1,2,\dots,n)~.

Các số trên cùng một dòng được cách nhau bởi dấu cách.

Output

Một số nguyên là số lượng cặp số nguyên ~(l,r)~ thỏa mãn yêu cầu.

Scoring

Sample Input 1

3
2 1 2

Sample Output 1

4

Sample Input 2

5
2 2 1 2 3

Sample Output 2

10

Notes

Trong ví dụ thứ nhất, các cặp ~(l,r)~ thỏa mãn là ~(1,1), (2,2), (3,3), (1,3)~.