配点 : 200 点
問題文
在数轴上 1,2, \ldots, N 并编号 N 有山羊。山羊 i 是起始坐标 我在 A_i 。在这里,山羊保证最初位于不同的坐标。
下面 Q 查询 请按以下顺序处理: i=1,2,\ldots,Q 。 老师将食物放在
座標 B_i 处,距离食物最近的山羊吃掉食物。然而,如果有不止一只这样的山羊,那么编号最低的山羊就会吃掉食物。另外,坐标 X 和坐标 Y 的距离是 给出 \lvert X-Y \rvert 。
找出吃每种食物的山羊数量。然而,吃完食物后,山羊会移动到食物所在的坐标并留在那里。
制約
- 1 \leq N,Q \leq 2 \times 10^5
- -10^{18} \leq A_i \leq 10^{18} (1 \leq i \leq N)
- A_i \neq A_j (1 \leq i < j \leq N)
- -10^{18} \leq B_i \leq 10^{18} (1 \leq i \leq Q)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \ldots A_N Q B_1 B_2 \ldots B_Q
出力
对于每个查询 打印行 1 上的答案。
入力例 1
5 10 7 21 2 13 4 11 9 17 16
出力例 1
1 1 3 3
1 第二个查询中,放置了诱饵 最接近 11 山羊在 10 山羊 1 吃食物, 11 。
2 在第三个查询中,放置了诱饵。 一只靠近 9 的山羊 有 7 山羊 2 和 按字典顺序比较 11 山羊 1 。因此,数字较小的山羊 给出了 1 吃食物, 9 。