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ố thứ tự từ 1 đến \(n\). Điều mà Mr Bin quan tâm đó chính là lá phiếu bầu của cư dân. Biết rằng mỗi cư dân đều có một nguyện vọng. Vì vậy, Mr Bin cần tổ chức một cuộc vận động để các cư dân trong làng bỏ phiếu cho mình. Anh ấy chỉ mời các cư dân trong làng có số thứ tự liên tiếp từ L đến R \((1 \leq L\ \leq \ R \leq n)\) tham gia cuộc vận động, để nêu ra chính sách của mình. Chính sách của anh ấy đưa ra chỉ phù hợp với một nhóm nhiều người nhất có cùng nguyện vọng. Cư dân nào thỏa mãn được nguyện vọng thì sẽ bỏ cho Mr Bin một phiếu bầu. Những người còn lại sẽ bỏ phiếu cho đối thủ duy nhất là Mr John.

Chú ý: Những người không được Mr Bin mời họ sẽ quên bỏ phiếu cho cả hai ứng cử viên là Mr Bin và Mr John. Mr Bin chỉ thắng cử khi có nhiều hơn nửa số phiếu bầu.

Vì vậy, Mr Bin quyết định mời các cư dân có số thứ tự trong đoạn từ L đến R, để triển khai chính sách của anh ấy.

Yêu cầu: Hãy cho biết có bao nhiêu cách chọn hai số L và R để Mr Bin thắng cử.

Dữ liệu vào:

- Dòng đầu tiên chứa một số nguyên dương n là số lượng người (1 ≤ n ≤ 200000).

- Dòng thứ hai chứa n số nguyên dương \(a_{i}\ (1\ \leq \ a_{i} \leq 10^{9};1 \leq i \leq n\ )\). Số \(a_{i}\) đại diện cho nguyện vọng của người thứ i.

Kết quả: Ghi một số nguyên duy nhất là số cách mà Mr Bin chọn hai số L và R để anh ấy thắng cử.

Ví dụ:

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).

Ràng buộc dữ liệu:

- Có 30% số test ứng với 1 ≤ n ≤ 300.

- Có 30% số test ứng với 1 ≤ n ≤ 2000.

- Có 40% số test còn lại không có ràng buộc gì thêm.