Cho 1 1 dãy số A A gồm N N phần tử a 1 , a 2 , . . . , a n a 1 ​ ,a 2 ​ ,...,a n ​ .

Yêu cầu Hãy cho biết tổng đoạn con từ vị trí x x tới vị trí y y của mảng Input Dòng đầu tiên là độ dài mảng N ( N ≤ 1 0 6 ) N(N≤10 6 ). Dòng thứ hai gồm N N chữ số A i ( A i ≤ 1 0 6 ) A i ​ (A i ​ ≤10 6 ). Dòng thứ ba là số truy vấn Q ( Q ≤ 1 0 6 ) Q(Q≤10 6 ). Q Q dòng tiếp theo mỗi dòng gồm 2 số x , y ( 1 ≤ x ≤ y ≤ N ) x,y(1≤x≤y≤N). Output Gồm nhiều dòng là kết quả bài toán. Sample 1 Input 6 1 2 3 2 1 2 3 1 3 2 4 1 6 Output 6 7 11