配列 \(A\) の指定位置に要素を挿入・取得するクエリは、 AVL 木などの平衡二分探索木を使うことで \(O(\log |A|)\) で処理できます。

よって本問題を \(O(N\log N)\) で解くことができました。

C++ の GCC を使う場合、 ext/rope が用意されているので、それを使うとよいです。詳しくは ここ を参照してください。