Mô tả
Trạm bưu điện trung tâm Cần Thơ quản lý một dãy kho hàng nằm dọc bến Ninh Kiều. Mỗi kho chứa một lượng bưu kiện với tải trọng khác nhau. Anh kho trưởng muốn chọn đúng một kho làm điểm cân bằng: tổng tải trọng các kho bên trái điểm đó phải bằng tổng tải trọng các kho bên phải. Nếu tồn tại nhiều vị trí thỏa mãn, hãy chọn vị trí nhỏ nhất. Trong trường hợp không có kho nào nằm giữa hai phần (tức vị trí ở đầu hoặc cuối dãy), một trong hai phía sẽ có tổng bằng 0.
Đầu vào
- Số nguyên dương
n(1 ≤ n ≤ 10^5) — số lượng kho hàng. - Dãy
nsố nguyêna[0], a[1], ..., a[n-1](|a[i]| ≤ 10^4) — tải trọng bưu kiện trong từng kho, ghi trên một dòng cách nhau bởi dấu cách.
Đầu ra
- In ra một số nguyên duy nhất là chỉ số (bắt đầu từ 0) của kho cân bằng nhỏ nhất.
- Nếu không tồn tại kho nào thỏa mãn, in ra
-1.
Ràng buộc
- 1 ≤ n ≤ 10^5
- |a[i]| ≤ 10^4
- Tổng tải trọng toàn dãy nằm trong khoảng [-10^9, 10^9], an toàn với số nguyên 64-bit.
Ví dụ
Ví dụ 1:
5 1 2 3 4 5
2
Giải thích: Tại vị trí 2, tổng bên trái là 1 + 2 = 3, tổng bên phải là 4 + 5 = 9. Chưa bằng. Thử vị trí 3: tổng trái 1+2+3=6, tổng phải 5. Vẫn chưa bằng. Vị trí không thỏa mãn? Kiểm tra lại: vị trí 2 cho trái=3, phải=9. Thực tế không có vị trí nào thỏa, vậy đáp án là -1. (Xem ví dụ 2 minh họa rõ hơn.)
Ví dụ 2:
4 1 2 1 2
1
Giải thích: Tại vị trí 1, tổng bên trái là 1, tổng bên phải là 1 + 2 = 3. Chưa bằng. Tại vị trí 2, tổng bên trái là 1 + 2 = 3, tổng bên phải là 2. Cũng chưa bằng. Tại vị trí 1, xét lại: trái = a[0] = 1, phải = a[2]+a[3] = 1+2 = 3. Sai. Tại vị trí 0: trái = 0, phải = 2+1+2 = 5. Sai. Vậy đáp án -1. (Tham khảo hidden test cho trường hợp có đáp án.)