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.

You are then given q query keys; each query key is guaranteed to already be present in the tree. For each query key x, report its in-order predecessor: the largest key in the tree that is strictly less than x. If x is the minimum key, report -1.

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 x_1 ... x_q, each equal to one of the n keys.

Output format

q lines. Line i contains the in-order predecessor of x_i, or -1 if x_i is the minimum key.

Constraints

• 1 ≤ n ≤ 40
• -1000 ≤ each key ≤ 1000, all keys distinct
• 1 ≤ q ≤ 40

5
5 3 8 1 4
3
3 1 8

1
-1
5

1
9
1
9

-1