Cho một dãy N số nguyên, mỗi số nằm trong khoảng từ 1 đến N. Ta cần dùng các khái niệm sau:

• Dãy con là một dãy gồm các phần tử liên tiếp trong dãy ban đầu.

• Một giá trị gọi là trội trong dãy K phần tử nếu như giá trị đó xuất hiện ít nhất [K/2] + 1 lần trong dãy đó, trong đó ký hiệu [x] là phần nguyên của x (số nguyên lớn nhất nhỏ hơn hoặc bằng x).

Yêu cầu: Tính số lượng dãy con có chứa giá trị trội trong dãy đã cho.

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương N ≤ 250000;

• Dòng thứ hai chứa N số nguyên, mỗi số trong khoảng từ 1 đến N, hai số liên tiếp được ghi cách nhau bởi dấu cách.

Kết quả

Đưa ra một số là số lượng dãy con có chứa giá trị trội tìm được.

Sample Input

6
1 2 1 2 3 2

Sample Output

10

Giải thích

-  Có 6 dãy con 1 phần tử, mỗi dãy đều thoả mãn dãy chứa giá trị trội;
- 4 dãy con còn lại chứa giá trị trội là những dãy được gạch chân dưới đây:
1 2 1 2 3 2
1 2 1 2 3 2
1 2 1 2 3 2
1 2 1 2 3 2
Hạn chế
ˆ Subtask 1: n ≤ 10000
ˆ Subtask 2: N ≤ 250000.