数列 \(A\) に対し問題文中の指示通りに操作を行うと、\(1\) 回の操作に \(\Theta(|A|)\) 時間かかるケースが存在するため、全体で \(\Omega(Q^2)\) 時間かかるケースが存在し TLEとなります。（\(|A|\) は数列 \(A\) の長さを表す）

この問題は双方向リストというデータ構造を用いて解くことができます。双方向リストとは直感的には、各要素が「自分の前の要素」と「自分の後の要素」の情報のみを持つデータ構造のことです。

要素の追加・削除を行うごとに、前後の要素の「自分の前の要素」「自分の後の要素」の情報を更新していきます。双方向リストの先頭から必要な値を探すと線形時間かかりますが、連想配列などを用いて値からリストのノードを高速に求められるようにしておくことで、全ての処理を高速に行うことができます。

例として、以下の入力に対しての処理を図示します。図ではわかりやすさのために 値を \(A\) 内での順に並べていますが、そうする必要はないことも確認してください。

3
3 1 4
2
1 1 2
2 3

以上を実装することでこの問題を解くことができます。 実装の際には先頭や末尾の要素が削除されるケースなどに注意してください。番兵を用意してもよいでしょう。

実装例(Python)