Задача "В дек-2!"

Задача такая же, как В дек!, однако N (количество операций) не превышает 500000. При этом гарантируется, что ни в какой момент в деке не будет находиться больше 100 чисел.

Реализуйте эту задачу, не заводя массива больше чем на 200 элементов.