输入的第一行包含一个正整数 n，表示序列长度。
输入的第二行包含 n 个整数 a1,a2,…,an。
输入的第三行包含一个正整数 q，表示询问次数。
输入的第 j+3 (1≤j≤q) 行包含两个正整数 Lj,Rj，表示第 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。

因此 k1=6，k2=6，k3=−1，k4=1。
对于第 2 次询问，k1=2，k2=2，k3=2，k4=2。
对于第 3 次询问，k1=6，k2=6，k3=2，k4=2。





特殊性质 A：对于所有 1≤j≤q，均有 Lj=Rj。
特殊性质 B：对于所有 1≤j≤q，均有 Rj≤32。
特殊性质 C：对于所有 1≤j≤q，均有 Lj≤16 且 Rj≥n−1000。
特殊性质 D：对于所有 1≤j≤q，均有 Lj>n/2。
特殊性质 E：对于所有 1≤j≤q，均有 Lj>n/4。


query.zip

NOIP 2025 第四题