Before going into the solution, consider this: For every query, count the number of element which are less than or equal to k,let us call it X. our answer for every query will be j-i+1-X

Now, to calculate the value of X:- - Declare an array A of size n. Initially all values zero. - Store the indexes of all the integers in a 2-D vector V. There can be at most n distinct integers. - Store all the queries in a vector and sort it according to k(ascending order). - Now iterate over query vector and for every number less than or equal to k, update the array for all the indexes stored in V for corresponding number. - Count the sum of elements in array A from i to j. X=sum(l,r) by Range sum query using segment tree or BIT. - Answer to each query=**j-i+1-X**

My code