D - ジャンプ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君が、一次元の無限に長い道路の上に立っている。すぬけ君は、N 種類のジャンプをすることができる。i 番目のジャンプでは、a_i に対して対称な位置にジャンプできる (場所 x にいるとき、場所 2a_i - x に移動する)。

Q 種類のクエリに答えよ。i 番目のクエリでは、s_i から t_i に行くのに最小何回ジャンプすればよいか求めよ。ただしジャンプだけで到達できない場合には、代わりに -1 と出力せよ。


Constraints

  • 1 \leq N \leq 200
  • 0 \leq a_1 < ... < a_N \leq 10000
  • 1 \leq Q \leq 100000
  • 0 \leq s_i, t_i \leq 10000

Input Format

入力は以下の形式で標準入力から与えられる。
N
a_1
:
a_N
Q
s_1 t_1
:
s_Q t_Q

Output Format

各クエリに対し、答えを一行に出力せよ。

Sample Input 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

Sample Output 1

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