题目描述

给定一个非降序排列的整数序列，要求在该序列中查找与给定值最接近的元素。若存在多个元素与给定值的距离相等（差值的绝对值相等），则输出其中最小的那个元素。

输入格式

1. 第一行：一个整数 $n$，表示非降序序列的长度，满足 $1 \leq n \leq 100000$。
2. 第二行：包含 $n$ 个整数，依次表示非降序序列中的各个元素，所有元素的取值范围是 $0 \sim 1000000000$。
3. 第三行：一个整数 $m$，表示要查询的给定值的个数，满足 $1 \leq m \leq 10000$。
4. 接下来 $m$ 行：每行一个整数，分别表示要查询最接近元素的给定值，所有给定值的取值范围是 $0 \sim 1000000000$。

输出格式

输出共 $m$ 行，每行一个整数，依次为与相应输入给定值最接近的元素值，保持输入顺序。

输入输出样例 #1

输入 #1

3
2 5 8
2
10
5

输出 #1

8
5

数据范围

• 对于 $100\%$ 的数据，$1 \leq n \leq 100000$，$1 \leq m \leq 10000$，非降序序列元素及给定值的范围均为 $0 \sim 1000000000$。