题目描述

在非降序排列的米粒数字序列中，对于给定的多个数字 m，找出每个 m 在序列中最接近的数字。若有多个数字同样接近，输出最小的那个。

输入格式

• 第一行：整数 n (1 ≤ n ≤ 100,000)，表示序列长度
• 第二行：n 个整数组成的非降序列 (0 ≤ 元素 ≤ 1,000,000,000)
• 第三行：整数 m (1 ≤ m ≤ 10,000)，表示查询次数
• 接下来 m 行：每行一个查询数字 (0 ≤ 数字 ≤ 1,000,000,000)

输出格式

• 对于每个查询数字，输出序列中最接近它的数字（若有多个同样接近，输出最小的）

样例

输入

3
2 5 8
2
10
5

输出

8
5