Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#55. 出栈序列判断

附加文件 统计

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

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

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

输入格式

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

输出格式

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

样例输入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$,输入一定是个合法的出栈序列。