1311: F-勇者斗恶龙

在很久很久以前，地上有一个荣光的王国，在这个王国里，国民安居乐业，国王开明勤政。但是突然有一天，有一群恶龙入侵了这个美丽的国家。恶龙们一路杀到了这个国家的首都，王国岌岌可危。

在这个生死攸关的时刻，王国的总共 $n$ 个勇者们聚集到了首都，在他们当中第 $i$ 个勇者的能力值为 $a_i$ ,这代表这个勇者能够对恶龙造成 $a_i$ 点伤害或者防御住恶龙 $a_i$ 的攻击。

与此同时，王国的勇士们获得了恶龙们的情报：在城外总共有 $m$ 条恶龙，第 $i$ 条恶龙的防御力为 $x_i$ ，攻击力为 $y_i$ 。幸运的是，恶龙们每次只会有一条来进攻首都。并且进攻的顺序为 $1$ 到  $m$

为了守住城堡，勇士们开始商量策略：

保险起见，勇士们决定每次只派一个勇士出去击杀恶龙，剩下的勇士们将留在城堡中守护首都。为了守住首都，出门迎战的勇士的能力值不能小于恶龙的防御力。而剩下的在首都的城堡里防御的勇士们的能力值之和不能小于恶龙的攻击力。

与此同时，国王拿出了一种神奇的药水（数量无限多），每一瓶药水能够让勇士的能力值短暂的提升 $1$ 点，药效只能保证勇士们应对一条恶龙，由于神奇药水的效果可以叠加（一个勇士可以同时喝 $k$ 瓶药增加 $k$ 点能力值）以及药水数量无限，我们就能保证勇士们一定可以守住每一条恶龙的进攻。

由于神奇药水非常宝贵，因此当然要尽可能少的使用。因为神奇药水的副作用极小，所以国王并不在意哪名勇士喝了多少瓶药水，但是国王想要知道对于每一条恶龙，勇士们至少需要多少瓶药水才能打败这一条恶龙？

第一行一个正整数 $n$ ，代表英雄的数量

第二行包括 $n$ 个正整数 $a_1,a_2,a_3, ... ,a_n$,代表每个勇士的能力值

第三行一个正整数 $m$，代表恶龙的数量

接下来的每一行包括两个正整数 $x_i,y_i$。代表第 $i$ 条恶龙的防御力和攻击力

输出为 $m$ 行，每行输出一个整数，代表击败第 $i$ 条恶龙至少需要的药水数量。

4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7

1
2
4
0
2

注意：请不要抄袭他人代码提交，所有的被OJ查重的代码即使正确也会被修改为答案错误


样例解释

对第 $1$ 条恶龙：我们给 $3$ 号勇士喝一瓶药，此时勇士们的能力值变为 $[3,6,3,3]$ ，我们让 $1$ 号勇士出城迎战恶龙，剩下的勇士留下守卫。因此答案为 $1$。

对第 $2$ 条恶龙：我们给 $2$ 号和 $3$ 号勇士喝药，此时勇士能力值变为 $[3,7,3,3]$ 我们让 $2$ 号勇士出城迎战恶龙，剩下的勇士守卫。因此答案为 $2 $。

对第 $3$ 条恶龙：我们给所有勇士喝药，此时勇士的能力值变为 $[4,7,3,4]$，我们让 $4$ 号勇士出城，剩下的勇士守卫。因此答案为 $4$ 。

对第 $4$ 条恶龙：不需要喝药水，勇士能力值为 $[3,6,2,3]$ ， 我们让$3$号勇士出城，剩下的勇士守卫。因此答案为 $0$。

对第 $5$ 条恶龙：我们让 $2$ 号勇士喝下 $2$ 瓶药，勇士能力值变为 $[3,8,2,3]$ ，我们让 $2$ 号勇士出城，剩下的勇士守卫，因此答案为$2$。


数据范围

对于 $20\%$ 的数据，$1≤n≤100 ， m = 1 ， 1 ≤ a_i , x, y ≤1000$

对于 $50\%$ 的数据，$1≤n,m≤1000 ， 1≤a_i,x ≤10^5 ， 1≤y≤10^9$

对于 $100\%$ 的数据$，1≤n,m≤10^5 ， 1≤a_i,x ≤10^9， 1≤ y ≤10^{15}，$