You are given n distinct integers. Starting from an empty binary search tree (BST), insert them in the order given, using the standard BST rule: to insert a key x, walk down from the root comparing x to the current node's key, going left if x is smaller and right if x is larger, until you reach an empty spot, where a new node is created. No rebalancing is ever performed.
You must then answer q independent rank queries. Query i gives an integer k_i (1-indexed); you must report the k_i-th smallest key currently stored in the tree (so k_i = 1 is the minimum key, k_i = n is the maximum key).
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 k_1 ... k_q.
Output format
q lines. Line i contains the k_i-th smallest key.
Constraints
- 1 ≤ n ≤ 40
- -1000 ≤ each key ≤ 1000, all keys distinct
- 1 ≤ q ≤ 40
- 1 ≤ k_i ≤ n for every query