Vị trí cân bằng của dãy

Bối cảnh

Trong một mô hình cân bằng tải tuyến tính, n trạm được đặt liên tiếp trên một tuyến. Giá trị tại mỗi trạm có thể dương hoặc âm và biểu diễn lượng tài nguyên đóng góp hoặc tiêu thụ. Một trạm i được gọi là vị trí cân bằng nếu tổng giá trị của tất cả trạm nằm hoàn toàn bên trái i bằng tổng giá trị của tất cả trạm nằm hoàn toàn bên phải i; giá trị của chính trạm i không thuộc bên nào.

Ban điều hành không chỉ muốn biết có tồn tại vị trí cân bằng hay không mà còn cần số lượng tất cả vị trí như vậy. Nếu có nhiều vị trí, báo thêm chỉ số nhỏ nhất để làm mốc kiểm tra đầu tiên. Nếu không có vị trí cân bằng, chỉ số báo cáo là -1.

Không nên tính lại tổng trái và tổng phải cho từng i bằng hai vòng lặp, vì cách đó che mất cấu trúc của bài. Tổng toàn dãy cho phép suy ra phía phải khi đã biết tổng phía trái.

Yêu cầu

1. Tính tổng toàn bộ dãy một lần.
2. Duy trì left là tổng các phần tử trước i.
3. Suy ra right = total - left - a[i]; so sánh, cập nhật count/first rồi cộng a[i] vào left.

Input

Dòng 1: n. Dòng 2: n số nguyên.

Output

Một dòng count firstIndex; nếu count=0 thì firstIndex=-1.

Ràng buộc

1 ≤ n ≤ 2000, |a[i]| ≤ 10^9.

Ví dụ 1

Input

5
1 3 5 2 2

Output

1 2

Giải thích

Tổng toàn dãy là 1+3+5+2+2 = 13. Ta xét từng index i và so sánh tổng bên trái với tổng bên phải, không tính a[i]. Tại i=2, tổng trái là 1+3 = 4 và tổng phải là 2+2 = 4, nên đây là vị trí cân bằng. Các index còn lại không cho hai tổng bằng nhau, vì vậy có đúng 1 vị trí cân bằng và vị trí đầu tiên là 2, tạo output 1 2.

Ví dụ 2

Input

1
7

Output

1 0

Giải thích

Dãy chỉ có một phần tử 7. Tại index 0, phía trái không có phần tử nên tổng trái bằng 0; phía phải cũng rỗng nên tổng phải bằng 0. Vì 0 = 0, index 0 là vị trí cân bằng duy nhất. Do đó output là 1 0.

Thông tin học tập

• Module: M03
• Buổi: B09
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: static arrays, total sum, running prefix, equilibrium index, tie-break
• Giới hạn kiến thức: B01-B09
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100