该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。 有 $q$ 次询问，其中第 $j$ ($1 ≤ j ≤ q$) 次询问将会给出 $L_j, R_j$ ($1 ≤ L_j ≤ R_j ≤ n$)。定义 区间 $[l, r]$ ($1 ≤ l ≤ r ≤ n$) 是极. 好. 的. ，当且仅当区间 $[l, r]$ 的长度在 $[L_j, R_j]$ 内，即 $L_j ≤ r−l+1 ≤ R_j$。定义区间 $[l, r]$ ($1 ≤ l ≤ r ≤ n$) 的权. 值. 为 $\sum_{i=l}^{r} a_i$。

对于所有 $i = 1, 2, \ldots, n$，求出所有包含 $i$ 的极好区间的最大权值，即

$$\max_{1≤l≤i≤r≤n} \left\{ \sum_{k=l}^{r} a_k \;\middle|\; L_j ≤ r-l+1 ≤ R_j \right\}.$$

输入格式

从文件 query.in 中读入数据。

• 第一行包含一个正整数 $n$，表示序列长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
• 第三行包含一个正整数 $q$，表示询问次数。
• 第 $j+3$ 行 ($1 ≤ j ≤ q$) 包含两个正整数 $L_j, R_j$，表示第 $j$ 次询问。

输出格式

输出到文件 query.out 中。 对于每次询问，设包含 $i$ ($1 ≤ i ≤ n$) 的极好区间的最大权值为 $k_i$，输出一行一个 非负整数：

$$\bigoplus_{i=1}^{n} \big((i \times k_i) \bmod 2^{64}\big),$$

其中 $\bigoplus$ 表示二. 进. 制. 按. 位. 异. 或.。注意：对于任意整数 $x$，存在唯一的非负整数 $x'$ 满足 $x' ≡ x \pmod{2^{64}}$ 且 $0 ≤ x' ≤ 2^{64}-1$，则记 $x \bmod 2^{64} = x'$。

样例 1 输入

4
2 2 4 -5 1
3
3 3
4 1 2
5 3 4
6 1 4

样例 1 输出

18446744073709551603
8
4

样例 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 = k_2 = k_3 = k_4 = 2$。

• 对于第 3 次询问，$k_1 = k_2 = 6, k_3 = 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 ∼ 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 ∼ 20$ 的约束条件。

数据范围

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

• $1 ≤ n ≤ 5 × 10^4$，$1 ≤ q ≤ 1024$；
• 对于所有 $1 ≤ i ≤ n$，均有 $|a_i| ≤ 10^5$；
• 对于所有 $1 ≤ j ≤ q$，均有 $1 ≤ L_j ≤ R_j ≤ n$。

特殊性质说明：

• A：对于所有 $1 ≤ j ≤ q$，均有 $L_j = R_j$。
• B：对于所有 $1 ≤ j ≤ q$，均有 $R_j ≤ 32$。
• C：对于所有 $1 ≤ j ≤ q$，均有 $L_j ≤ 16$ 且 $R_j ≥ n - 1000$。
• D：对于所有 $1 ≤ j ≤ q$，均有 $L_j > n/2$。
• E：对于所有 $1 ≤ j ≤ q$，均有 $L_j > n/4$。