First until there are two equal elements erase both of them. Now if we are left with less than $$$50$$$ elements we can for each $$$x$$$ calculate $$$(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$$$ directly and check if it equals 0.

If not we compute prefix xors, to be able to compute in constant time parity of numbers in any interval. Now for each $$$x$$$ we iterate over all bits $$$b$$$ such that $$$2^b \geq x$$$ in decreasing order and for each we want to know parity of count of numbers such, that $$$b$$$-th bit is set in $$$a_i \mod (x + 1)$$$. To do this we can run through all intervals $$$[l, r) = [a(x + 1), (a + 1)(x + 1))$$$ and in each of them set of numbers with $$$b$$$-th bit set is exactly $$$[l + b, l + 2b), [l + 3b, l + 4b), \ldots, [l + (2k+1)b, r)$$$, which is $$$1$$$ interval on first run with largest possible $$$b$$$ at most $$$2$$$ on second, $$$4$$$ on third etc. Now since $$$k$$$ is large, the function $$$(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$$$ looks random, so on average the first run will happen for each $$$x$$$, second for half of them, third for one fourth, and so on, which adds to total $$$O(n \log ^2 n)$$$

Except it's bullshit, because for example if after erasing numbers we are left with integers from $$$[4\cdot 10^5, 5\cdot 10^5)$$$ if we pick $$$x$$$ such that $$$2x \leq 4\cdot 10^5, 3x \gt 5\cdot 10^5$$$, we're left with numbers from $$$[4\cdot 10^5 - 2x, 5\cdot 10^5 - 2x)$$$, which is sequence of consecutive numbers of length divisible by $$$4$$$, least of which is even, so since $$$2x \oplus (2x + 1) \oplus (2x + 2) \oplus (2x + 3) = 0$$$ their xor is $$$0$$$, so my solution will run through all iterations for all such $$$x$$$-es and will take total of $$$O(n^2)$$$.

Fortunately there were only random testcases, so reasoning based on randomness of function $$$(a_1 \mod x) \oplus (a_2 \mod x) \oplus \ldots \oplus (a_k \mod x)$$$ holds.