Maximum Queue Operations

You are given a data structure called MaxQueue that supports the following operations:

• enqueue: Insert an integer at the end of the queue.
• dequeue: Remove the integer at the front of the queue and print it.
• getMax: Print the maximum integer currently present in the queue.

Your task is to process a sequence of these operations. For every operation dequeue and getMax you must print the corresponding output on a new line.

The operations must be implemented efficiently. One recommended approach is to use a double-ended queue (deque) to maintain the current maximum. Formally, if you denote the queue as \(Q\) and the auxiliary deque as \(D\), then:

[ \text{enqueue}(x): \quad Q.push_back(x), \quad \text{while } D\text{ is not empty and } D.back() < x \text{ do } D.pop_back(), \quad D.push_back(x). ]

[ \text{dequeue}(): \quad x = Q.pop_front(); \quad \text{if } x = D.front() \text{ then } D.pop_front(); \quad \text{return } x. ]

[ \text{getMax}(): \quad \text{return } D.front(). ]

Implement the MaxQueue to support these operations and process the given commands accordingly.

inputFormat

The first line contains an integer (n) denoting the number of operations. Each of the following (n) lines contains an operation. An operation is one of the following formats:

• enqueue X where (X) is an integer to insert into the queue.
• dequeue which removes and prints the element at the front of the queue.
• getMax which prints the current maximum element in the queue.

It is guaranteed that all dequeue and getMax operations are valid (i.e. the queue is not empty when these operations are invoked).

outputFormat

For each dequeue and getMax operation, print the returned value on a new line in the order they appear in the input.## sample

5
enqueue 1
getMax
enqueue 2
getMax
dequeue

1
2
1