灰灰的玩具

灰灰的玩具

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

今天名飞送给了灰灰一个神奇的玩具。
这个玩具由两个量筒和一行排列好的共\(N\)个数字块组成。

名飞事后跟我说量筒是他从化学实验室偷出来的,还偷了浓硫酸,以后的题目会出现。

灰灰可以把数字块放入量筒,但是当量筒中有多个数字块的时候,灰灰只能先拿出最上面的数字块,再依次拿下面的。(Stack后进先出)
名飞交给了灰灰一个小任务,让他在遵守量筒的后进后出的规则下,对这行数字块进行排序,使得最后所有数字块从量筒中拿出来后组成的序列单调递增。

具体来说共四个操作:

  • 操作a:将最前面的数字块放入量筒1。
  • 操作b:将量筒1的最顶端数字块拿出,放到数字块序列尾部。
  • 操作c:将最前面的数字块放入量筒2。
  • 操作d:将量筒2的最顶端数字块拿出,放到数字块序列尾部。

输入格式

第一行是一个整数\(n\)。
第二行有\(n\)个用空格隔开的正整数,构成一个\(1\)∼\(n\)的排列。

输出格式

共一行,如果输入的排列无法排序,输出0
否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

样例

输入

4
1 3 2 4

输出

a b a a b b a b

数据规模

\(n \leqslant 1000\)

来源

洛谷P1155

AKIOI Round #0 入门赛

未参加
状态
已结束
规则
OI
题目
10
开始于
2023-10-08 18:00
结束于
2023-10-08 22:00
持续时间
4.0 小时
主持人
参赛人数
1