← 返回题目列表

AtCoder · pakencamp_2024_day1_e

E. 山羊

中文机器翻译题面 查看原题

配点 : 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 。