does a program with order O(n*max(K)) can get accepted.
A modified version of bubble sort can do this.Note that
after k passes bubble sort has first k maximum elements.
If u find maximum value of index that is being queried and calling the below function with that maximum value will do the trick for you.Try submitting the problem using this idea.I haven't submitted by this idea
for(i=0;i<=k;i++)
    for(j=i+1;j<n;j++)
          if(a[i]>a[j]) swap(a[i],a[j]);