出栈序列判断

题目描述

现在有一个栈，有 $n$ 个元素，分别为 $1, 2, \dots, n$。我们可以通过 push 和 pop 操作，将这 $n$ 个元素依次放入栈中，然后从栈中弹出，依次把出栈的元素写下来得到的序列就是出栈序列。

比如 $n=3$，如果执行 push 1, push 2, pop, push 3, pop, pop，那么我们 pop 操作得到的元素依次是 $2, 3, 1$。也就是说出栈序列就是 $2, 3, 1$。

现在给定一个合法的出栈序列，请输出一个合法的由 push 和 pop 操作构成的操作序列。这里要求 push 操作一定是按 $1, 2, \dots, n$ 的顺序。

输入格式

第一行一个整数 $n$。接下来一行 $n$ 个整数，表示出栈序列。

输出格式

输出 $2n$ 行，每行一个 push 或 pop 操作，可以证明一个出栈序列对应的操作序列是唯一的。

样例输入 1

3
2 3 1

样例输出 1

push 1
push 2
pop
push 3
pop
pop

样例输入 2

5
1 3 5 4 2

样例输出 2

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

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 100000$，输入一定是个合法的出栈序列。