Queue with Maximum

In this problem, you are required to implement a queue data structure that, in addition to the standard operations, supports a query to retrieve the current maximum element in the queue efficiently.

The supported operations are:

• 1 x: Enqueue the integer \(x\) into the queue.
• 2: Dequeue the front element from the queue and output it. If the queue is empty, output Error.
• 3: Output the maximum element in the queue. If the queue is empty, output Empty.

Your solution should process each operation in \(O(1)\) amortized time. A common approach to achieve this is by maintaining an auxiliary deque that keeps candidate maximum values in decreasing order. The maximum element is always at the front of this auxiliary deque, and when dequeuing an element, if it is equal to the maximum, you should remove it from the auxiliary structure.

For a sequence of numbers \(a_1, a_2, \dots, a_n\), the maximum is given by \(\max_{1 \leq i \leq n} a_i\).

inputFormat

The first line contains an integer \(Q\) (1 ≤ \(Q\) ≤ 10⁵), denoting the number of operations.

Each of the following \(Q\) lines contains one of the following commands:

• 1 x where \(x\) is an integer (\(|x| \leq 10^9\)); this command enqueues \(x\) into the queue.
• 2; this command dequeues the front element from the queue and prints it. If the queue is empty, print Error.
• 3; this command prints the maximum element in the queue. If the queue is empty, print Empty.

outputFormat

For each operation of type 2 or 3, output a single line with the result. For the 2 command, print the dequeued element. For the 3 command, print the current maximum in the queue. If an operation is invalid due to an empty queue, output the corresponding error message.

## sample

5
1 3
1 1
3
2
3

3
3
1

</p>