Smallest unreachable subsequence sum

Time limit2sMemory limit512 MB

Summary

For each subarray, find the smallest non-negative integer that no subsequence sums to.

Level: Hard9 of 10
Topics: Segment tree, Greedy, Sorting
Solved: No attempts yet

Problem

You are given a sequence $A$ of length $N$ . A subsequence is what is left after deleting some elements of $A$ , and deleting every element is allowed, so the empty sequence is a subsequence too. The sum of a subsequence is the sum of the integers it keeps, and the sum of the empty subsequence is 0.

For example, if $A$ is [1, 1, 3, 7], the subsequences [], [1], [1, 1], [3], [1, 3], [1, 1, 3] have sums 0, 1, 2, 3, 4, 5 in that order. No subsequence sums to 6, so the smallest non-negative integer that is not a subsequence sum of $A$ is 6.

Then $M$ queries are given. Each query consists of two integers $L$ and $R$ and asks for the smallest non-negative integer that is not the sum of any subsequence of $A_L, A_{L+1}, \dots, A_R$ . Write a program that answers every query.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 100000$ ). The second line contains the sequence $A_1, A_2, \dots, A_N$ . Every number is a natural number at most $10^9$ , and the sum of all numbers in the sequence is also at most $10^9$ .

The third line contains the number of queries $M$ ( $1 \le M \le 100000$ ). Each of the next $M$ lines contains one query in the form $L_i$ $R_i$ ( $1 \le L_i \le R_i \le N$ ).

Output

Print the answer to each query on its own line, in the order the queries are given.

Examples8

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3
Input
```
1
1
1
1 1
```
Expected output
```
2
```
Example 4
Input
```
1
1000000000
1
1 1
```
Expected output
```
1
```

Example 5

Input

10
1 1 1 1 1 1 1 1 1 1
8
1 1
1 10
3 7
5 5
2 3
1 9
10 10
4 10

Expected output

Example 6

Input

29
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456
8
1 29
1 1
2 29
1 28
5 10
29 29
1 20
10 29

Expected output

Example 7

Input

6
5 3 2 7 2 4
6
1 6
2 2
3 3
1 3
4 6
2 5

Expected output

Example 8

Input

8
1 1 1 100 1 2 4 1
8
1 8
4 4
1 3
4 8
1 4
5 8
2 7
3 6

Expected output