链接: https://cses.fi/problemset/task/2402

板块: Additional Problems II

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个由 $n$ 个数组成的输入序列，1 到 $n$ 的每个整数恰好出现一次。

你的任务是用两个栈生成排好序的输出序列。每一步你可以做以下之一：

• 把输入序列的第一个数移入某个栈；
• 把某个栈的栈顶数移到输出序列末尾。

输入

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数：输入序列的内容。

输出

输出 $n$ 个整数：每个数被移入的栈编号（1 或 2）。你可以输出任意合法解。如果没有解，输出 IMPOSSIBLE。

数据范围

$1 \le n \le 2 \cdot 10^5$

样例输入

5
2 3 1 5 4

样例输出

1 2 1 1 2