I came up with the following problem a few days ago and I didn't manage to solve it in a better complexity than O(NlgN + QN), maybe you can help as I'm stuck and starting to think it's impossible:

You're given an array of N elements, and Q queries. Each query consists of a single integer X, and you're asked to determine if there's a pair of integers in the array whose sum is X, or if there isn't any.

I didn't determine any bounds, but the less, the better. some bounds can be on the maximal value of an element in the array, I don't mind, as long as someone finds a solution better than mentioned earlier. Would also be better if the algorithms will be able to output the indicies of the 2 integers with sum X.

I'd also be happy if someone proves it to be impossible.