存在 $\mathcal O(\sqrt n \log n)$ 的做法。轻松拿下最优解。

不过因为偷懒，所以只写了 cpp 的代码。