Chia dãy số

Tin học trẻ không chuyên khối THPT - Bắc Giang 2015 - Bài 1/4
Cho dãy N số nguyên dương a1, a2, ..., an (dãy A). Một cách chia dãy với chỉ số k thành hai phần là a1, a2, ... a(k-1) và ak, a(k+1), ..., an
Yêu cầu: Có thể chia dãy A thành hai phần sao cho tổng các phần tử của chúng bằng nhau được hay không?
Dữ liệu vào: Từ tệp văn bản CHIADAY.INP gồm:
     Dòng 1 ghi số nguyên N (1<= N <=10^6);
     Dòng thứ hai ghi các số nguyên ai (i lần lượt từ 1 đến N, 1<= ai <= 10^6), các số cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản CHIADAY.OUT gồm một số nguyên duy nhất là chỉ số k nếu tìm được cách chia, ghi số -1 nếu không tìm được cách chia.
Ví dụ:
    CHIADAY.INP              CHIADAY.OUT
      5                                            4
      1 2 3 7 1

      6                                            -1
      1 1 2 3 7 9

                                                           Lời giải tham khảo