Mr Bin đang chạy đua trong cuộc bầu cử ở làng X. Ngôi làng gồm \(n\) người, được đánh số từ 1 đến \(n\).

Mỗi cư dân có một nguyện vọng - được biểu diễn bởi một số nguyên dương. Mr Bin tổ chức một cuộc vận động và chỉ mời các cư dân trong một đoạn liên tiếp từ \(L\) đến \(R\) để trình bày chính sách của mình.

Chính sách này sẽ phù hợp nhất với một nhóm nhiều người nhất có cùng nguyện vọng trong đoạn \([L, R]\). Tất cả cư dân trong đoạn này có nguyện vọng khớp với chính sách sẽ bỏ phiếu cho Mr Bin. Những người còn lại (trong đoạn đó) sẽ bỏ phiếu cho Mr John.

Những người ngoài đoạn \([L, R]\) sẽ không bỏ phiếu cho ai.

Điều kiện thắng cử:

• Mr Bin chỉ thắng cử nếu số phiếu ông nhận được lớn hơn một nửa tổng số phiếu (tức là số người trong đoạn \([L, R]\) chia đôi).

Yêu cầu:

• Hãy đếm số cách chọn đoạn \([L, R]\) (\(1 \le L \le R \le n\)) sao cho Mr Bin thắng cử.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \le n \le 200000\)) - số cư dân trong làng.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) (\(1 \le a_i \le 10^9\)), biểu diễn nguyện vọng của từng cư dân.

Dữ liệu ra:

• In ra một số nguyên duy nhất là số đoạn \([L, R]\) mà nếu chọn đoạn đó để vận động, Mr Bin sẽ thắng cử.

Input 1

5
3 3 2 3 4

Output 1

10

Giải thích:

• Với dữ liệu vào thứ nhất ta có thể chọn các cặp chỉ số sau: (1,1), (2,2), (3,3), (4,4), (5,5), (1,2), (1,3), (1,4), (1,5), (2,4).

Input 2

5
3 3 2 2 4

Output 2

10

Ràng buộc:

• Có 30% số test ứng với \(1 \le n \le 300\).
• Có 30% số test ứng với \(1 \le n \le 2000\).
• Có 40% số test còn lại không có ràng buộc gì thêm.