Snuke 站在一条无限长的道路上。 这条道路上的位置由实数表示。 Snuke 可以进行 $N$ 种跳跃。第 $i$ 种跳跃是关于点 $a_i$ 对称的。也就是说，如果他在点 $x$ 处进行这种跳跃，他将跳到 $2a_i - x$。 给定 $Q$ 次询问。在第 $i$ 次询问中，你需要计算 Snuke 从 $s_i$ 到 $t_i$ 所需的最少跳跃次数。如果通过一系列跳跃无法从 $s_i$ 到达 $t_i$，则输出 $-1$。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 200$)。接下来的 $N$ 行每行包含一个整数 $a_i$ ($0 \le a_1 < \dots < a_N \le 10^4$)。下一行包含一个整数 $Q$ —— 询问次数 ($0 \le Q \le 10^5$)。接下来的 $Q$ 行中，每行包含一个询问，由两个整数 $s_i$ 和 $t_i$ ($0 \le s_i, t_i \le 10^4$) 组成。

输出格式

对于每次询问，在一行中输出答案。

样例

输入 1

4
1
2
4
7
10
2 3
5 6
6 0
3 7
10 3
7 6
5 5
2 10
4 10
10 10

输出 1

-1
-1
2
2
-1
-1
0
3
1
0