There are N buildings stand along the horizon line. Each building are 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⁶, both Ai and h is positive integer and ≤ 10⁹.

Input

N
A1 A2 ... An
M
(here following the M queries.)

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