問題文

KowerKoint 君は競技プログラミングのコンテストに出場し、そこでは以下の問題が出題されました。

正整数 N と、正整数からなる長さ N の数列 A=(A_1, A_2, \dots, A_N) が与えられる。 A の最大値を正整数 m で割った余りを求めて出力せよ。

KowerKoint 君は A の要素を m で割った余りの最大値を求めて出力するコードを提出しました。これは問題に対して正しいプログラムではありませんが、このコンテストの作問者はテストケースを一つしか用意しなかったため、奇跡的に正解（の値を出力）することができました。作問者が用意したテストケースの N と A が与えられます。クエリが Q 個与えられます。 q 番目のクエリでは m として考えられる正整数のうち、 M_q 以下のものの個数を求めてください。

制約

• 1 \leq N \leq 200{,}000
• 1 \leq N \times A_i \leq 2 \times 10^{10}
• 1 \leq Q \leq 200{,}000
• 1 \leq M_q \leq 10^{18}
• 入力はすべて整数

小課題

1. (1 点) N \leq 100, A_i \leq 100

2. (99 点) 追加の制約はない

入力例 1

2
1 3
2
4
2

出力例 1

3
2

1 つめのクエリの場合、 m として 1,2,4 の 3 通りが考えられます。

このテストケースは小課題 1 の制約を満たします。

入力例 2

5
1 2 6 7 10
3
5
18
30

出力例 2

1
10
22

このテストケースは小課題 1 の制約を満たします。