If you naively apply the operations instructed in the problem statement against the sequence \(A\), an operation may cost \(\Theta(|A|)\) time, for a total of \(\Omega(Q^2)\), which result in TLE (Time Limit Exceeded). (\(|A|\) denotes the length of \(A\).)

This problem can be solved with a data structure called doubly linked list. A doubly linked list is intuitively a data structure where each element maintains only the element immediately before and after itself.

Whenever an element is inserted or removed, update the “previous element” and the “next element” of its adjacent element accordingly.

For example, we illustrate the process against the following input. For clarity, the values are arranged in the order within \(A\), but notice that it is not mandatory.

3
3 1 4
2
1 1 2
2 3

This way, the problem can be solved. When implementing, notice that the first or last element may be removed. It may be a good idea to use sentinels.

Sample code (Python)