rt，本题可以用逐块处理的 trick 轻松做到 $O(n)$ 空间，建议加强数据卡掉调块长过的 $O(n\sqrt n)$ 空间做法或者缩小空间到 $15mb$。