Highest average <Nissan>
Problem
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≤N,Q≤5∗105
- 1≤Ai,K≤109
Time Limit: 2
Memory Limit: 256
Source Limit:
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}.
