AKVISM02 - Butters Counting Problem

no tags 

Cartman got a really easy task. Butters just gave "N" numbers (Ai: 0 <= i < N) in non-decreasing order to Cartman, and then asked him to count the numbers that are smaller than or equal to "L". Cartman did the task easily. But Butters being a wicked kid, suddenly started giving him a huge amount of very large numbers. Cartman could not complete the task on time, so he wants your help to complete the task as fast as possible.

Input

First line will contain "N". The next line will contain "N" numbers (Ai : 0 <= i < N) in non-decreasing order. The next line will contain "Q", the number of queries asked by Butters. Each of the next "Q" lines contain "L", the query from Butters.

Output

For each "L", output the count of numbers that are less than or equal to "L" on a separate line.

Constraints

1 <= N <= 100000

0 <= Ai <= 10^9

1 <= Q <= 100000

0 <= L <= 10^9

Example

Input:
10
1 2 2 5 7 9 10 13 15 15
5
0
2
1
10
18

Output:
0
3
1
7
10

hide comments
Anant Kumar: 2013-08-02 12:21:10

Finally!!!


Added by:Ankit Kumar Vats
Date:2013-07-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self