#10110. [NOIP2025] 序列询问

给定一个长度为 的整数序列 。

有 次询问，其中第 () 次询问将会给出 ()。定义区间 () 是极好的，当且仅当区间 的长度在 内，即 。定义区间 () 的权值为 。对于所有 ，求出所有包含 的极好区间的最大权值，即 。

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

输入的第二行包含 个整数 。

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

输入的第 () 行包含两个正整数 ，表示第 次询问。

对于每次询问，设包含 () 的极好区间的最大权值为 ，输出一行一个非负整数，表示 ，其中 表示二进制按位异或。注意：对于任意整数 ，存在唯一的非负整数 满足 且 ，则记 。

输入 #1

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

输出 #1

18446744073709551603
8
4

【样例 1 解释】

对于第 次询问：

• 包含 的极好区间为 和 ，权值分别为 ；
• 包含 的极好区间为 ， 和 ，权值分别为 ；
• 包含 的极好区间为 ， 和 ，权值分别为 ；
• 包含 的极好区间为 和 ，权值分别为 。

因此 ，，，。

对于第 2 次询问，，，，。

对于第 3 次询问，，，，。

【样例 2】

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

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

【样例 3】

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

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

【样例 4】

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

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

【样例 5】

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

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

【样例 6】

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

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

【样例 7】

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

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

【样例 8】

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

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

【数据范围】

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

• ，；
• 对于所有 ，均有 ；
• 对于所有 ，均有 。

特殊性质 A：对于所有 ，均有 。

特殊性质 B：对于所有 ，均有 。

特殊性质 C：对于所有 ，均有 且 。

特殊性质 D：对于所有 ，均有 。

特殊性质 E：对于所有 ，均有 。