Mô tả và yêu cầu

Cho một dãy n số nguyên dương ai (n ≤ 105, ai ≤ 109).
Yêu cầu: Có t truy vấn t ≤ 106, mỗi truy vấn gồm hai số nguyên dương i và j yêu
cầu in ra tổng của các số trong đoạn ai, ai+1, …, aj.
Dữ liệu vào: Từ thiết bị nhập chuẩn gồm
 Dòng đầu tiên chứa số nguyên n.
 Dòng thứ hai chứa n số nguyên a1, a2, ... an.
 Dòng thứ ba chứa số nguyên t.
 t dòng tiếp theo, mỗi dòng chứa 2 số nguyên i và j tương ứng với các
truy vấn cần tính tổng của các số nguyên trong đoạn ai, ai+1, ..., aj.
Kết quả: Ghi ra thiết bị xuất chuẩn gồm các tổng cần tìm, mỗi số trên một dòng
tương ứng với các truy vấn cần tìm.

Ví dụ

INPUT                           OUTPUT
                 6                              9
                 2 3 4 5 1 8                    18
                 3                              13
                 3 4
                 3 6
                 2 5