Create an unordered map <int, set <int> > and for each number in the input insert it's index to the corresponding position in the map, then for each query use manipulations with upper_bound in the set.

Looks like O(nlogn + qlogn).

Edited by author 13.08.2015 20:29