Trong một vương quốc xa xôi, có một con đường dài với ~n~ cột mốc được đánh số từ 1 đến ~n~. Mỗi cột mốc đều được khắc một con số tượng trưng cho quan điểm của người dân tại vị trí đó.

Nhà vua muốn tìm ra những đoạn liên tiếp trên con đường mà trong đó có một quan điểm áp đảo, tức là có một số xuất hiện nhiều hơn hoặc bằng một nửa số các số được khắc trên các cột mốc của đoạn đó.

Yêu cầu: Hãy xác định có bao nhiêu cách chọn hai cột mốc ~L~ và ~R~ (~1 \le L \le R \le n~) sao cho đoạn từ cột mốc ~L~ đến ~R~ thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 200000~) là số lượng cột mốc trên con đường.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 10^9~) là con số được khắc trên từng cột mốc.

Output

• Ghi ra một số nguyên duy nhất là số cách chọn đoạn con thỏa mãn điều kiện trên.

Sample Input 1

5
3 3 2 3 4

Sample Output 1

10