题目背景

感谢 @FFjet 提醒，第 8 个数据点损坏暂时删除。

题目描述

W 师兄计划了很久，终于成功的在 BG 开了一家寿司店。

正当W师兄还在兴奋的时候，这时一个噩耗传来，吃货L师姐居然知道了这件事，而且正赶过来，W 师兄瞬间心就冷了下去，但是机智的 W 师兄也瞬间想到了应付 L 师姐的策略.......

这时，L 师姐到了寿司店，先四处望了望风景，发现现在只有 L 师姐一个顾客，下面是 L 师姐的选餐说明：

1.寿司店内的寿司被排在一行共 $N$ 个盘子里，按从左到右编号为 $1$~$N$。

2.每个位置上寿司的数量是确定的并且有玻璃窗保护。

3.每隔一段时间就会有一个选餐时间，L 师姐可以在一个连续的区间 $[l, r]$ 中选择其中一盘，然后在该区间之外选择另一盘（如果区间外有盘子）。

L 师姐发现这家寿司店厨师的制作速度很快，总能在下一次选餐时间前将寿司数量恢复原样。

作为有尊严有追求的吃货，L 师姐也有自己的规则，L 师姐在选完两盘寿司后，会决定每口恰好吃 $D$ 个寿司，且使得两盘寿司刚好可以分别吃完，不剩余任何寿司。比如两盘寿司数量为 $2$ 和 $4$，那么 $D=1$ 或者 $D=2$ 都可以恰好将两盘寿司分别吃干净，而两盘寿司数量为 $3$ 和 $5$ 时，那么只能 $D=1$ 才行。

作为有特殊追求的 L 师姐才不在乎吃的数量，L 师姐在乎的是一口吃多个寿司的感觉。于是，如果 L 师姐可以一口吃 $D$ 个寿司，那么 L 师姐的愉悦值为 $D$，但是 L 师姐没有选到两盘寿司，那么她的愉悦值为 $0$。

现在 L 师姐知道每个盘子所放着的寿司数量，L 师姐想知道每次选择时间过后她可以获得的最大愉悦值是多少？

输入格式

第一行输入一个整数 $N$，表示寿司的盘子数量。

第二行输入 $N$ 个整数 $a_1,a_2,\cdots,a_N$，$a_i$ 表示第 $i$ 个盘子内的寿司数量。

第三行输入一个整数 $M$，表示有多少个选餐时间。

接下来 $M$ 行，每行两个整数 $l_i, r_i (1 \le l_i \le r_i \le N)$，含义如题面所示。

输出格式

输出 $M$ 行，第 $i$ 行表示第 $i$ 个选择时间师姐可能达到的最大愉悦值 $D$。

5
1 2 3 4 5
2
2 3
2 4

2
1

5
2 4 8 16 32
2
3 4
2 3

16
8

提示

###样例解释

样例 $1$ 里的第一个选餐时间，可以选择 $2$ 和 $4$，这样 L 师姐就可以每次吃两个寿司，使得两个盘子都可以吃干净，第二个选餐时间，师姐不管选哪两个盘子，都只能每次吃一个。

样例 $2$ 里的第一个选餐时间，可以选择 $16$ 和 $32$，而第二个选餐时间，L 师姐可以选择 $8$ 和 $16$ 或者 $8$ 和 $32$。

对于 $20\%$ 的数据，$N \le 100, M \le 100, \max(a_1,a_2,\cdots,a_N) \le 100$。

对于 $50\%$ 的数据，$N \le 10000, M \le 10000, \max(a_1,a_2,\cdots,a_N) \le 10000$。

对于 $100\%$ 的数据，$N \le 10^5, M \le 10^5, \max(a_1,a_2,\cdots,a_N) \le 10^5$。