题目描述

Snuke 站在一条无限长的路上。

在这条路上的位置用一个实数表示。

Snuke 可以进行 $N$ 次跳跃。类型为 $i$ 的跳跃相对于点 $a_i$ 的跳跃是对称的。也就是说，如果他在点 $x$ 上执行这种跳跃，他将跳跃到 $2a_i - x4$)。

给您 $Q$ 次查询。在第 $i$ 次查询中，要求您计算 Snuke 从 $s_i$ 到 $t_i$ 必须执行的最少跳跃次数。如果通过一系列跳转无法从 $s_i$ 达到 $t_i$，则打印$-1$。

【简要题意】

在数轴上有 $n$ 个跳跃重心 $a_{1}, a_{2}, \ldots, a_{n}$ 。你可以从 $x$ 点一步跳到 $2 a_{i}-x$ 点。

有 $q$ 次询问, 每次给出起点 $S$ 和终点 $T$ , 问从 $S$ 到 $T$ 最少需 要跳几步, 无解输出 $-1$ 。

$1 \leq n \leq 200,0 \leq a_{i}, S, T \leq 10^{4}, 1 \leq q \leq 10^{5}$。

输入格式

输入的第一行包含一个整数 $N(1 \leq N \leq 200)$。接下来的 $N$ 行包含整数 $a_{i}$，每行一个 $ \left(0 \leq a_{1}<\ldots<a_{N} \leq 10^{4}\right) $。下一行包含一个整数 $Q$ 查询次数 $\left(0 \leq Q \leq 10^{5}\right)$。接下来的每一行 $Q$ 都包含一个查询，由两个整数 $s_{i}$ 和 $t_{i}\left(0 \leq s_{i}, t_{i} \leq 10^{4}\right)$ 组成。

输出格式

对于每个查询, 在一行中打印答案。

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
2
2
-1
-1
0
3
1
0