Description

Snuke is standing on an infinitely long road.

The position on this road is represented by a real number.

Snuke can perform $N$ types of jumps. The jump of type $i$ is symmetric with respect to the point $a_i$. That is, if he performs this jump at point $x$, he will jump to $2a_i − x4).

You are given $Q$ queries. In the $i$-th query, you are asked to compute the minimum number of jumps Snuke must perform to go from $s_i$ to $t_i$. If $t_i$ is unreachable from $s_i$ by performing a series of jumps, print $−1$ instead.

Input

First line of the input contains one integer $N(1 \leq N \leq 200)$ . Next $N$ lines contain integers $a_{i}$ , one per line $ \left(0 \leq a_{1}<\ldots<a_{N} \leq 10^{4}\right) $. Next line contains one integer $Q$ the number of queries $\left(0 \leq Q \leq 10^{5}\right)$ . Each of the next $Q$ lines contains one query and consists of two integers $s_{i}$ and $t_{i}$ $\left(0 \leq s_{i}, t_{i} \leq 10^{4}\right)$.

Output

For each query, print the answer in a single line.

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