Một dãy số gồm ~ N ~ phần tử được gọi là “tốt” nếu mỗi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá ~ N/2 ~ .

Ví dụ:

• [1, 1, 2, 3, 5], [6, 4, 10, 6] và [1, 2] là các dãy tốt.

• [3, 3, 3, 4, 4], [7, 7, 8, 7] và [100] không phải là các dãy tốt.

Cho dãy ~ A ~ độ dài ~ N ~, hãy đếm số cặp chỉ số ~ (l, r) ~ với (~ 1 ≤ l ≤ r ≤ N ~) sao cho dãy con ~ A_l, A_{l+1}, . . . , A_r ~ là dãy tốt

Input

• Dòng đầu tiên gồm số nguyên ~ N ~ (~ 1 ≤ N ≤ 500 000 ~) — độ dài dãy A

• Dòng thứ hai gồm ~ N ~ số nguyên ~ A_1, A_2, . . . A_N ~ (~ 1 ≤ A_i ≤ 500 000 ~) — các phần tử của dãy A.

Output

• Một số nguyên duy nhất là số cặp chỉ số ~ (l, r) ~ thỏa mãn yêu cầu đề bài.

Sample

Input #1

4
2 1 1 3

Output #1

3

Input #2

5
1 1 3 2 2

Output #2

6

Input #3

6
1 2 1 2 1 2

Output #3

9

Hint

• Ở ví dụ thứ nhất, có 3 cặp chỉ số (l, r) thỏa mãn yêu cầu đề bài:

– l = 1, r = 2 (dãy [2, 1])

– l = 1, r = 4 (dãy [2, 1, 1, 3])

– l = 3, r = 4 (dãy [1, 3])

• Ở ví dụ thứ hai, có 6 chỉ số (l, r) thỏa mãn yêu cầu đề bài:

– l = 1, r = 4 (dãy [1, 1, 3, 2])

– l = 1, r = 5 (dãy [1, 1, 3, 2, 2])

– l = 2, r = 3 (dãy [1, 3])

– l = 2, r = 4 (dãy [1, 3, 2])

– l = 2, r = 5 (dãy [1, 3, 2, 2])

– l = 3, r = 4 (dãy [3, 2])

Problem source: Free Contest 100