# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are given an array A of length N. You have to choose a subset S from given array A, such that average of S is less than K. You need to print the maximum possible length of S.

**Input format :**

• The first line of each input contains N, length of array A.

• Next line contains N space separated elements of array A.

• Next line of input contains an integer Q, Number of queries.

• Each following Q lines contains a single integer K.

**Output format :**

• For each query, print single integer denoting the maximum possible length of the subset.

**Constraints :**

1<=N,Q<=5*10^5

1<=A[i],K<=10^9

Input | Output |
---|---|

5 1 2 3 4 5 5 1 2 3 4 5 | 0 2 4 5 5 |

**Explanation**

In first query, there is no possible subset such that its average is less than 1.

In second query, you can select the subset {1,2}.

In third query, you can select the subset {1,2,3,4}.

In fourth and fifth query, you can seelct the complete array {1,2,3,4,5}.

60% Solution Ratio

Fazlerabbi.Earliest,

pathanFastest, 0.3s

Fazlerabbi.Lightest, 9.4 MB

jaberndcShortest, 437B

Login to submit