P4587 [FJOI2016] Mysterious Number

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$.

- 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$.

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

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