PROGRAMMING:Special stack

Stack is a classic linear structure of last in first out. The related operations mainly include "in stack" (insert an element at the top of stack) and "out stack" (return the top of stack element and delete it from the stack). This problem requires you to implement another additional operation: "take the median" - that is, to return the median value of the key value of all elements in the stack. Given n elements, if n is an even number, then the median value is defined as the nth / 2nd small element; If it is odd, then it is the (n + 1) / 2 small element.
###Input format:
The first line of input is a positive integer n ($$\ Le 10 ^ 5 $$). Then n lines, each line gives an instruction, which is one of the following three types:
```
Push key
Pop
PeekMedian
```
Where 'key' is a positive integer no more than $$10 ^ 5 $` "Push" means "put on stack"` Pop 'means "out of stack"` Peekmedian means "take the median".
###Output format:
For each 'push' operation, the 'key' is inserted into the stack without output; For each 'pop' or 'peekmedian' operation, the corresponding return value is output in one line. If the operation is illegal, the corresponding output is' invalid '.
###Input example:
```in
seventeen
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
```
###Output example:
```out
Invalid
Invalid
three
two
two
one
two
four
four
five
three
Invalid
```







answer：If there is no answer, please comment