ヒント → https://atcoder.jp/contests/arc149/editorial/4868

[1] 観察

すべての初期位置 \(1, 2, \ldots, 10^6\) に対する結果を計算しましょう．初期位置が \(x\) であるようなコマに番号 \(x\) をつけておきます．

これらのコマの動きを観察しましょう． はじめ，\(10^6\) 個のコマは座標が正の部分に番号順に隣接して並んでいます．この状態ではコマの番号と座標の関係も単純ですし，次の移動先もまとめて簡単に扱えます．

\(1\) 回目の移動により，コマの列が，負の部分・原点・正の部分に分断されます．原点に来たコマについてはそれ以上計算する必要はないので，負の部分・正の部分について考えましょう．正の部分だけ・負の部分だけであれば \(2\) 回目の移動も同じ式で表されるためまとめて扱えそうですが，正の部分・負の部分では座標変化の式が異なるのが厄介です．これらもうまくまとめて扱う方法を考えましょう．

[2] 解法

ある時点で座標 \(x\) にあるコマと座標 \(-x\) にあるコマについては，以降の動作は原点について対称になります．よってこれら \(2\) つのコマについては，片方は以降の移動の計算は不要で，もう片方のみの移動を計算すればよいことになります．

すると，負の部分のコマの列・正の部分のコマの列のうち，短い方の列に属するコマは，以降の移動の計算は不要になります．したがって，以下のことを適切に実装すればこの問題を解くことができます．

• 座標が定符号であるようなコマの列について，コマの番号と座標の関係を保持しながら，移動をシミュレートしていく．
• 原点に到達したコマがあるとき，そのコマについての答を確定させ，以降のそのコマに関する移動の計算は行わない．
• コマの列が正の部分・負の部分に分断されたとき，短い方に属するコマについては，対称な位置にあるコマの番号を記録して，以降それらのコマに関する移動の計算は行わない．このコマについては，すべての移動が終わったあとで，記録したコマの番号を元に答を求める．

「答を確定させる」「対称な位置にあるコマの番号を記録する」という操作は合計でコマの総数と同じ回数しか行われないため，時間計算量 \(O(M + \max X_i)\) で解くことができます．

より詳しくは，正の部分・負の部分に分断されたときには，短い列の各コマから対称なコマの番号を求め，その番号のコマに（有向）辺を張ることを考えます．コマ全体は有向森をなします．すべての移動が終わったあと，その根から順に答を伝搬させていくことで，すべてのコマに対する答を求めることができます．次の画像も参考にしてください．

解答例

https://atcoder.jp/contests/arc149/submissions/35220962