Description

The mysterious number of a multiset $S$ is defined as the smallest positive integer that cannot be represented as the sum of a submultiset of $S$. For example, with $S = \{1,1,1,4,13\}$, we have: $1 = 1$, $2 = 1+1$, $3 = 1+1+1$, $4 = 4$, $5 = 4+1$, $6 = 4+1+1$, $7 = 4+1+1+1$.

$8$ cannot be represented as the sum of a submultiset of $S$, so the mysterious number of $S$ is $8$.

You are given a sequence $a$ of length $n$ consisting of positive integers, and $m$ queries. Each query contains two parameters $l, r$. You need to find the mysterious number of the multiset formed by $a_l, a_{l+1}, \cdots, a_r$.

Input Format

• The first line contains an integer $n$, the number of elements.
• The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, indexed from $1$.
• The third line contains an integer $m$, the number of queries.
• Each of the next $m$ lines contains two integers $l, r$.

Output Format

For each query, output one line with the corresponding answer.

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

2
4
8
8
8

Hint

For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $\sum a_i \le 10^9$.

Translated by ChatGPT 5