Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Joker là một kẻ quái dị, hắn thử thách tình yêu của Harley Quinn đủ mọi cách. Giờ Joker lại nghĩ một trò chơi mới để chơi đùa với Harley Quinn. Joker cho Harley Quinn một tập hợp n số a[1], a[2], …, a[n] và yêu cầu như sau:

Harley Quinn phải chọn hết các tập con của tập đã cho (tập con có thể rỗng), với mỗi tập con, cô phải tính tổng các phần tử của tập con đó.

Sau khi có được tổng tất cả các tập con, Harley Quinn phải cho Joker biết số nguyên dương nhỏ nhất không xuất hiện trong tập kết quả mà cô vừa tính được.

Ví dụ: cho tập S = {1, 4} ta sẽ có các tập con:

S0 = {}, sum = 0.

S1 = {1}, sum = 1.

S2 = {4}, sum = 4.

S3 = {1, 4}, sum = 5.

Vậy số nguyên dương nhỏ nhất không xuất hiện là 3.

Tuy nhiên, bài toán này vẫn chưa đủ khiến Joker cảm thấy thú vị, hắn tăng tiếp độ khó của bài toán, với một thay đổi nhỏ, hắn vẫn sẽ hỏi kết quả của bài toán trên nhưng trên q dãy con, mỗi dãy con gồm các phần tử liên tiếp của dãy a đã cho. Để tăng sự căng thẳng, hắn tự tay gắn lên người Harley Quinn một quả bom, nếu cô trả lời chậm, hắn sẽ kích hoạt quả bom đó.

Harley Quinn cũng vừa cứu thế giới khỏi tay của Enchantress, các bạn hãy giúp cô ấy nhé. 

Input

Dòng đầu tiên là số nguyên n – số lượng phần tử của dãy a (1 <= n <= 10^5)

Dòng thứ hai chứa n số nguyên a[1], a[2], …, a[n] (1 <= a[i] <= 10^9), tổng tất cả các phần tử cũng không vượt quá 10^9.

Dòng thứ ba chứa số nguyên q – số lượng dãy con mà Joker sẽ hỏi Harley Quinn (1 <= q <= 10^5)

q dòng tiếp theo, dòng thứ i chứa cặp số nguyên L[i], R[i] (1 <= L[i] <= R[i] <= n) với ý nghĩa dãy con mà gã hề hỏi sẽ gồm các số nguyên a[L[i]], a[L[i] + 1], …, a[R[i]].

Output

Gồm q dòng, dòng thứ i là đáp án của bài toán với dãy con thứ i.

Example

Input:
5
1 3 2 2 5
1
2 4

Output:
1