Monk and his friend Micro are on a quest to find the answer of Life, Universe and Everything. In order to complete it they need to answer Q queries on an array A having N integers. The queries can be of following two types:
\(0 \space x:\) Find the number of numbers in A which are not less than x.
\(1 \space x:\) Find the number of numbers in A which are greater than x.
Help them complete the quest and be back in time for the next Code Monk Challenge.

Input Format:
First line consists of a single integer denoting N.
Second line consists of N space separated integers denoting the array A.
Third line consists of a single integer denoting Q.
Each of the following Q lines consists of a query of one of the given two types.

Output Format:
For each query print the required answer in new line.

Constraints:
\(1 \le N \le 10^5\)
\(1 \le Q \le 3 \times 10^5\)
\(1 \le A[i], x \le 10^9\)