Description

There are N buildings stand along the horizon line. Each building are been represented as a vertical segment with two end points at (i, 0) and (i, Ai). There are M queries in total. For each query, we wonder know how many buildings you can see if you stand at (0, h).

.. N, M ≤ 10^6, both Ai && h is positive interger and ≤ 10^9 .. .

Input

n
A1 A2 ... An
m ... (here following the m query.)

Output

... (for each query, simply print how many buildings you can see. )

Example

Input:
5
2 3 3 3 4
3
3
2
4

Output:
3
2
5