输入的第一行包含一个正整数 n，表示序列长度。

输入的第二行包含 n 个整数 a_1, a_2, \ldots, a_n。

输入的第三行包含一个正整数 q，表示询问次数。

输入的第 j + 3 (1 \le j \le q) 行包含两个正整数 L_j, R_j，表示第 j 次询问。

说明/提示

【样例 1 解释】

对于第 1 次询问：

• 包含 1 的极好区间为 [1,1] 和 [1,2]，权值分别为 2,6；
• 包含 2 的极好区间为 [1,2]，[2,2] 和 [2,3]，权值分别为 6,4,-1；
• 包含 3 的极好区间为 [2,3]，[3,3] 和 [3,4]，权值分别为 -1,-5,-4；
• 包含 4 的极好区间为 [3,4] 和 [4,4]，权值分别为 -4,1。

因此 k_1 = 6，k_2 = 6，k_3 = -1，k_4 = 1。

对于第 2 次询问，k_1 = 2，k_2 = 2，k_3 = 2，k_4 = 2。

对于第 3 次询问，k_1 = 6，k_2 = 6，k_3 = 2，k_4 = 2。

【样例 2】

见选手目录下的 query/query2.in 与 query/query2.ans。

该样例满足测试点 2,3 的约束条件。

【样例 3】

见选手目录下的 query/query3.in 与 query/query3.ans。

该样例满足测试点 4 的约束条件。

【样例 4】

见选手目录下的 query/query4.in 与 query/query4.ans。

该样例满足测试点 6,7 的约束条件。

【样例 5】

见选手目录下的 query/query5.in 与 query/query5.ans。

该样例满足测试点 8 \sim 10 的约束条件。

【样例 6】

见选手目录下的 query/query6.in 与 query/query6.ans。

该样例满足测试点 11,12 的约束条件。

【样例 7】

见选手目录下的 query/query7.in 与 query/query7.ans。

该样例满足测试点 13 的约束条件。

【样例 8】

见选手目录下的 query/query8.in 与 query/query8.ans。

该样例满足测试点 16 \sim 20 的约束条件。

【数据范围】

对于所有测试数据，均有：

• 1 \le n \le 5 \times 10^4，1 \le q \le 1,024；
• 对于所有 1 \le i \le n，均有 |a_i| \le 10^5；
• 对于所有 1 \le j \le q，均有 1 \le L_j \le R_j \le n。

特殊性质 A：对于所有 1 \le j \le q，均有 L_j = R_j。

特殊性质 B：对于所有 1 \le j \le q，均有 R_j \le 32。

特殊性质 C：对于所有 1 \le j \le q，均有 L_j \le 16 且 R_j \ge n - 1000。

特殊性质 D：对于所有 1 \le j \le q，均有 L_j > n/2。

特殊性质 E：对于所有 1 \le j \le q，均有 L_j > n/4。