Stack Maximum Query

You are given a series of operations to be performed on a stack. The operations include inserting (pushing) an integer onto the stack, removing (popping) the top element, and querying for the maximum element in the stack.

Your task is to implement the stack so that these operations are executed in O(1) time. More specifically, when a query operation is issued, you should output the current maximum element, denoted as \(\max(S)\) where \(S\) represents the set of elements in the stack. If the stack is empty during a query, print Empty.

inputFormat

The input is given via standard input. The first line contains an integer (n) representing the number of operations. Each of the following (n) lines contains one operation in one of the following formats:

- + x: Push the integer (x) onto the stack.
- -: Pop the top element from the stack.
- ?: Print the maximum element in the stack. If the stack is empty, output Empty.

outputFormat

For each query operation (i.e. lines starting with ?), output the current maximum element on a separate line. If the stack is empty when a query is performed, output Empty.## sample

2
+ 1
? 

1