You are given n distinct integers. Starting from an empty binary search tree, insert them in the order given, using the standard BST rule: to insert a key x, walk down from the root, going left if x is smaller than the current node and right if x is larger, until an empty spot is reached, where a new node is created. No rebalancing is performed.
For each of q target values t, find the key in the tree whose absolute difference from t is smallest. If two keys are equally close, report the smaller of the two.
Input format
Line 1: an integer n.
Line 2: n space-separated distinct integers — the keys, in insertion order.
Line 3: an integer q.
Line 4: q space-separated integers t_1 ... t_q — the query targets.
Output format
q lines. Line i contains the key closest to t_i (smaller key wins ties).
Constraints
- 1 ≤ n ≤ 40
- -1000 ≤ each key ≤ 1000, all keys distinct
- 1 ≤ q ≤ 40
- -2000 ≤ t_i ≤ 2000