Note that the remaining number is kept $1008$ times as the larger one of the pair. So it is bigger than at least $2^{1008}-1$ numbers.

Similarly, the remaining number is kept $1008$ times as the smaller one of the pair so it is smaller than at least $2^{1008}-1$ numbers.

Therefore, the remaining number $x$ satisfies
$$2^{1008} \leq x \leq 2^{2016} - 2^{1008} + 1.$$
To prove that any $x$ satisfies the above inequalities is true, we can carry out the pairing inductively so that after $2i$ steps, the following condition is satisfied: if the numbers remaining are
$$a_{1} < a_{2} < \ldots < a_{2^{2(n-i)}}$$
then $x$ is one of these, and there are at least $2^{n-i}-1$ numbers smaller than $x$ and at least $2^{n-i}-1$ numbers larger than $x$. $\square$