Offline: sort queries by k, and initialize a fenwick tree with an array of length n initially filled with zeros. Then, keep a pointer to a sorted version of the original array, and as elements become \leq k for the k of the current query, set the value at the element’s index in the fenwick tree to 1. Then just do a sum query on the query’s range.
Online: do the same thing, but with a persistent segment tree. Or use a wavelet tree (the link in the blog doesn’t work, but read the comments or look stuff up further). For updates, a mergesort tree will work (note that you’ll need a PBDS set in each node instead of a vector).