← 返回题目列表

Codeforces · 1032/C

C. 弹钢琴

中文机器翻译题面 查看原题

小保罗想学弹钢琴。他已经有了想要开始的旋律。为了简单起见,他将这段旋律表示为一系列键号 $$$a_1, a_2, \ldots, a_n$$$:数字越多,它就越靠近钢琴键盘的右端。

Paul 非常聪明,他知道最重要的是正确地将手指分配给他要演奏的音符。如果他选择了不方便的指法,他就会浪费很多时间去学习如何用这些手指来演奏旋律,而且他很可能不会成功。

让我们用从 $$$1$$$ 到 $$$5$$$ 的数字来表示手的手指。我们将任何手指编号序列 $$$b_1, \ldots, b_n$$$ 称为指法。如果对于所有 $$$1\leq i \leq n - 1$$$ 满足以下条件,则指法是方便的:

- 如果 $$$a_i < a_{i+1}$$$ 则 $$$b_i < b_{i+1}$$$,否则 Paul 需要将手从键盘上拿开才能弹奏 $$$(i+1)$$$-st 音符;
- 如果 $$$a_i > a_{i+1}$$$ 则 $$$b_i > b_{i+1}$$$,因为相同;
- 如果 $$$a_i = a_{i+1}$$$ 则 $$$b_i\neq b_{i+1}$$$,因为连续两次使用同一个手指是愚蠢的。请注意,$$$b_i$$$ 和 $$$b_{i+1}$$$ 之间存在 $$$\neq$$$,而不是 $$$=$$$。

请提供任何方便的指法或查明没有。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 表示音符数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) 表示音符在键盘上的位置。

输出

如果没有方便的指法,则打印$$$-1$$$。否则,打印$$$n$$$数字$$$b_1,b_2,\ldots,b_n$$$,每个数字从$$$1$$$到$$$5$$$,表示方便的指法,用空格分隔。

示例

输入 #1

5
1 1 4 2 2

输出 #1

1 4 5 4 5

输入 #2

7
1 5 7 8 10 3 1

输出 #2

1 2 3 4 5 4 3

输入 #3

19
3 3 7 9 8 8 8 8 7 7 7 7 5 3 3 3 3 8 8

输出 #3

1 3 4 5 4 5 4 5 4 5 4 5 4 3 5 4 3 5 4

注意

第三个样本测试是 Reflex 的“Non stop”歌曲。