Highest average
82% Success5952 Attempts20 Points2s Time Limit256MB Memory1024 KB Max Code

Problem Statement :

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 \le N,Q \le 5*10^{5}\)
  • \(1 \le A_{i},K \le 10^{9}\)

 

Examples
Input
5
1 2 3 4 5
5
1
2
3
4
5
Output
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}.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results