Điểm chia cân bằng tốt nhất

Bối cảnh

Một tuyến vận chuyển gồm n kho nằm theo thứ tự. Do hệ thống phải chia tuyến thành hai khu vực liên tiếp để giao cho hai đội vận hành, cần chọn một điểm cắt sau vị trí p (0 ≤ p < n-1). Đội thứ nhất nhận các kho từ 0 đến p, đội thứ hai nhận các kho từ p+1 đến n-1. "Tải" của mỗi đội là tổng giá trị các kho thuộc khu vực đó.

Mục tiêu là chọn điểm cắt sao cho chênh lệch tuyệt đối giữa hai tổng nhỏ nhất. Nếu có nhiều điểm cắt cùng độ lệch tối ưu, chọn p nhỏ hơn. Bài toán có vẻ yêu cầu tính hai tổng cho từng p, nhưng tổng toàn dãy và một biến prefix chạy là đủ để đánh giá mỗi điểm cắt trong O(1).

Đây là bài tối ưu trên n-1 lựa chọn. Không cần mảng prefix đầy đủ nếu chỉ quét điểm cắt từ trái sang phải.

Yêu cầu

1. Tính total.
2. Duy trì left; tại mỗi p cộng a[p], suy ra right=total-left.
3. Tính abs(left-right) và cập nhật best; do quét p tăng dần, chỉ cập nhật khi diff nhỏ hơn.

Input

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

Output

Một dòng p minDifference.

Ràng buộc

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

Ví dụ 1

Input

5
1 2 3 4 5

Output

2 3

Giải thích

Ta thử điểm chia p giữa a[p] và a[p+1]. Với dãy 1 2 3 4 5, các chênh lệch |sumLeft-sumRight| lần lượt là 13 tại p=0, 9 tại p=1, 3 tại p=2 và 5 tại p=3. Giá trị nhỏ nhất là 3 ở p=2, tương ứng bên trái có tổng 1+2+3=6 và bên phải 4+5=9. Vì vậy output là 2 3.

Ví dụ 2

Input

2
10 1

Output

0 9

Giải thích

Dãy có hai phần tử nên chỉ có một điểm chia hợp lệ là p=0. Tổng bên trái là 10, bên phải là 1, độ lệch tuyệt đối bằng |10-1|=9. Không có phương án khác để so sánh, nên kết quả là 0 9.

Thông tin học tập

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