Stack Pop Sequence Judgment

Problem Description

There is a stack with $n$ elements, namely $1, 2, \dots, n$. By performing push and pop operations, we can push these $n$ elements into the stack one by one, then pop them out, and the sequence of popped elements written down in order is the pop sequence.

For example, when $n = 3$, if we perform push 1, push 2, pop, push 3, pop, pop, the elements we get from the pop operations are $2, 3, 1$ in order. That is, the pop sequence is $2, 3, 1$.

Now you are given a valid pop sequence. Please output a valid operation sequence consisting of push and pop operations. Here the push operations must be performed in the order $1, 2, \dots, n$.

Input Format

The first line contains an integer $n$. The next line contains $n$ integers, representing the pop sequence.

Output Format

Output $2n$ lines, each containing one push or pop operation. It can be proved that the operation sequence corresponding to a pop sequence is unique.

Sample Input 1

3
2 3 1

Sample Output 1

push 1
push 2
pop
push 3
pop
pop

Sample Input 2

5
1 3 5 4 2

Sample Output 2

push 1
pop
push 2
push 3
pop
push 4
push 5
pop
pop
pop

Constraints

For $100\%$ of the data, $1 \le n \le 100000$, and the input is guaranteed to be a valid pop sequence.