The mystic number of a multiset of numbers $S$ is defined as the smallest positive integer that cannot be represented as the sum of a subset of $S$. For example, if $S = \{1, 1, 1, 4, 13\}$, then: $1 = 1$ $2 = 1+1$ $3 = 1+1+1$ $4 = 4$ $5 = 4+1$ $6 = 4+1+1$ $7 = 4+1+1+1$ Since $8$ cannot be represented as the sum of a subset of $S$, the mystic number of $S$ is $8$.

Given $n$ positive integers $a[1] \dots a[n]$ and $m$ queries, for each query given by an interval $[l, r]$ ($l \le r$), find the mystic number of the multiset formed by $a[l], a[l+1], \dots, a[r]$.

Input

The first line contains an integer $n$, representing the number of integers. The second line contains $n$ integers, indexed from $1$. The third line contains an integer $m$, representing the number of queries. The following $m$ lines each contain a pair of integers $l, r$, representing a query.

Output

For each query, output the corresponding answer on a new line.

Examples

Input 1

5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

Output 1

2
4
8
8
8

Constraints

For $10\%$ of the data, $n, m \le 10$. For $30\%$ of the data, $n, m \le 1000$. For $60\%$ of the data, $n, m \le 50000$. For $100\%$ of the data, $n, m \le 100000$, $\sum a[i] \le 10^9$.