23. 寻找图书馆

单点时限: 2.0 sec

内存限制: 256 MB

有 (n) 个城市,编号依次分别为 (0) 到 (n - 1)。已知编号相邻的两座城市之间有一条长度为 1 的路。

其中有 (m) 个城市(分别为 (x_1, x_2, \ldots, x_m)),已经建立了图书馆。对于每次查询,输出距编号为 (k) 的城市最近的图书馆的距离是多少。

输入格式

第一行两个整数 (n) 和 (m)。

第二行 (m) 个数 ((1 \leq m \leq n)),代表有图书馆的城市的编号 (x_1, x_2, \ldots, x_m),保证不重复。

第三行一个整数 (q),表示查询次数。接下来 (q) 行,每行一个整数,表示询问编号为 (k) 的城市。

输出格式

(q) 行,每行一个整数,代表离最近的图书馆的距离。

样例

Input
5 2
0 4
2
1
2
Output
1
2

提示

测试点 n m q 特殊性质
1 \leq 1000 \leq min\{n, 1000\} =1
2×
3=10^5
4×
5 \leq 10^5 =1
6 = 2 \cdot 10^5
7 \leq \min \{n, 10^5\} ×
8 =10^9
9
10

注:特殊性质是指 (0) 和 (n-1) 一定有图书馆。

36 人解决,92 人已尝试。

48 份提交通过,共有 376 份提交。

6.1 EMB 奖励。

创建: 3 年,5 月前.

修改: 3 年,1 月前.

最后提交: 4 周,1 天前.

来源: N/A

题目标签