Each program need to have runtimes < n^2 to satisfy the runtime efficiency of some of the testsets. The following things are required before submission: The input of the programs need to be a text file passable by an argument.

public static void main(String[] args) { Scanner sc = new Scanner(new File(args[0])); ... }

Question 4: Shades for Summer We have a cool boy who wants to buy new shades for summer. He goes to a shop which contains N shades, where the prices are given in an array A. The price of i th shade is A[i]. Now our cool boy has q queries, in which he wants to know the number of shades that have price less than the given amount M.

Input:

First line contains N which denotes the total number of shades available in the shop

Second line contains the array A, N space separated integers Third line contains Q number of queries

Next Q lines contain integer M which denotes the query

Output: For each query output number of soaps having price less than M for that query.

Constraints:

1. 1 ? N ? 10^5

2. 1 ? A[i] ? 10^9

3. 1 ? Q ? 10^5

4. 1 ? M ? 10^5

input file

5

1 4 10 5 6

5

1

2

3

5

11

output:

0

1

1

2

5