题目描述

数轴上有 $N$ 座房屋，编号为 $1,2,\ldots,N$。第 $i$ 座房屋位于坐标 $X_i$。保证对于每个 $i$（$1\le i\le N-1$），都有 $X_i<X_{i+1}$。

对于满足 $1\le a<b\le N$ 的整数 $a,b$，若满足以下条件，则称连续的房屋 $a,a+1,\ldots,b$ 构成一个对称房屋区间：

• 对于每个 $i=0,1,\ldots,b-a$，都有 $X_a+X_b=X_{a+i}+X_{b-i}$。

给定 $Q$ 次询问，请依次处理。

• 在第 $i$ 次询问中，给定整数 $l_i,r_i$（$1\le l_i<r_i\le N$）。考虑所有满足 $l_i\le s<t\le r_i$，且连续的房屋 $s,s+1,\ldots,t$ 构成对称房屋区间的整数对 $(s,t)$，输出这些区间的宽度 $X_t-X_s$ 的最大值。

输入格式

输入包含一组测试数据，格式如下：

N
X_1 X_2 ... X_N
Q
l_1 r_1
l_2 r_2
...
l_Q r_Q

第一行包含一个整数 $N$，表示房屋数量（$2\le N\le 2\times 10^5$）。

第二行包含 $N$ 个整数 $X_1,X_2,\ldots,X_N$，表示房屋的坐标（$-10^9\le X_i\le 10^9$）。保证对于每个 $i$（$1\le i\le N-1$），都有 $X_i<X_{i+1}$。

第三行包含一个整数 $Q$，表示询问次数（$1\le Q\le 2\times 10^5$）。

接下来 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 次询问所指定范围的左右端点（$1\le l_i<r_i\le N$）。

输出格式

对于每次询问，输出最大可能宽度。

7
-5 -2 0 4 6 9 12
5
1 7
2 6
3 7
4 7
3 6

14
8
6
6
4