Store the state inside the cylinder in the Run Length encoding.

In other words, store the state after the following queries

1 2 3
1 3 4
1 10 10

in the format of “\(3\) twos, \(4\) threes, and \(10\) tens.” Since each query increments the length of this list by at most \(1\), so the length does never exceed \(Q\) overall.

By storing the information of this format, each insertion query can be processed in an \(O(1)\) time, and each take-out query in an \(O(1+(\text{the number of elements removed from the deque}))\). Therefore, the problem has been solved in a total of \(O(Q)\) time.

Note that this problem can in fact be solved without the Run Length encoding. For example, the state of the cylinder after the queries

1 10 3
1 10 10

is encoded as “\(13\) tens,” but we can just keep it as “\(10\) tens, and \(3\) tens” without changing the complexity from \(O(Q)\).