Một dãy số nguyên được coi là có số chính nếu có một giá trị xuất hiện trong dãy nhiều hơn một nửa độ dài dãy.
Cho dãy số nguyên \(a_1,a_2,…,a_n\), hãy xác định số lượng đoạn con của dãy có số chính.

Input

• Dòng 1: số nguyên \(n\ (1≤n≤3×10^5 )\);
• Dòng 2: \(n\) số nguyên \(a_1,a_2,…,a_n\) \((1≤a_i≤n ∀i)\).

Output

• Dòng \(1\): số nguyên là số đoạn con của dãy \(a_1,a_2,…,a_n\) có số chính.

Example

6
1 2 1 2 1 2

12