题目描述

给定一个长度为 $n$ 的输入序列，其中 $1$ 到 $n$ 的每个整数恰好出现一次。

你需要使用两个栈生成一个有序输出序列。每一步可以执行以下两种操作之一：

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

输入格式

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

第二行包含 $n$ 个整数，表示输入序列。

输出格式

输出 $n$ 个整数，第 $i$ 个整数为 $1$ 或 $2$，表示输入序列中第 $i$ 个数被移动到哪个栈。

可以输出任意一种合法方案；如果不存在方案，输出 IMPOSSIBLE。

数据范围

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

样例

样例输入

5
2 3 1 5 4

样例输出

1 2 1 1 2