题目描述

众所周知，天才程序员菜哭武是一个伟大的厨师。这天，张老师和石头来到菜哭武家做客，想尝一尝菜哭武的手艺。

菜哭武手上有 $n$ 种食材，每种食材个数无限多，编号为 $i$ 的食材有一个美味度 $a_i$。一道菜中，每种编号的食材至多有一个，而这道菜的美味度是这道菜包含的食材的美味度之和。

每次张老师会指定一个编号 $l$，石头会指定一个编号 $r$（$l \leq r$），然后菜哭武会在编号在 $[l, r]$ 中的食材中选若干种食材做菜。张老师和石头都是美食家，因此他们要求菜哭武依次做出美味度以 $1$，$2$，$3$，$4$……这样依次加 $1$ 递增的菜，直到菜哭武用当前的食材无法做出美味度为 $x$ 的菜。比如，某一个 $[l, r]$ 中的食材的美味度依次为 $2$, $1$, $1$, $1$, $7$，那么美味度为 $1$, $2$, $3$, $4$, $5$ 的菜都是可以做出来的，而美味度为 $6$ 的菜是无法做出来的，所以对于这对 $[l, r]$，$x = 6$。

张老师和石头一共会提出 $m$ 个这样的 $[l, r]$ 区间，对于每个区间，菜哭武想知道这个 $x$ 是多少。

输入格式

第一行一个整数 $n$（$1 \leq n \leq 10^5$），代表食材的个数。

第二行 $n$ 个整数，用空格隔开，第 $i$ 个整数 $a_i$ 代表编号为 $i$ 的食材的美味度。（$\sum a_i \leq 10^9$）

第三行一个整数 $m$（$1 \leq m \leq 10^5$），代表区间的个数。

接下来 $m$ 行，每行一对整数 $l$, $r$，代表一个区间。（$1 \leq l \leq r \leq n$）

输出格式

对于每一个区间，输出一行对应的答案。

样例输入

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

样例输出

3
8
3
19
1
35