Given an array of N elements and Q queries. Each query containing an integer X. For each query print the X^th smallest number of the input array.

Note : Don't use any predefined function. Try to make your own code.

Constraints
1 <= N <= 10⁵
1 <= Value of element of array <= 10¹⁸
1 <= Q <= 10⁶
1 <= X <= N

Input
First line contains value N. Next line contains N integers separated by a single space. Third line contains value Q. Next line contains Q integers separated by a space.