CF486E LIS of Sequence

下一次"数据结构与算法"课程将讲解序列的最长上升子序列（简称 LIS）。为了更好地理解，Nam 决定提前几天学习这个概念。 Nam 创建了一个包含 $n$ 个元素（$1 \leq n \leq 10^5$）的序列 $a$，元素分别为 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^5$）。一个子序列 $a_{i1}, a_{i2}, ..., a_{ik}$（其中 $1 \leq i_1 < i_2 < ... < i_k \leq n$）如果满足 $a_{i1} < a_{i2} < ... < a_{ik}$，则称之为上升子序列。而最长上升子序列是指在所有上升子序列中长度最长的。 Nam 意识到一个序列可能有多个最长上升子序列。因此，他将所有下标 $i$（$1 \leq i \leq n$）分为三类： 1. 不属于任何最长上升子序列的 $a_i$ 对应的下标 $i$； 2. 属于某些但不是全部最长上升子序列的 $a_i$ 对应的下标 $i$； 3. 属于每一个最长上升子序列的 $a_i$ 对应的下标 $i$。 由于序列 $a$ 的最长上升子序列数量可能非常庞大，分类过程十分困难。你的任务是帮助他完成这项工作。

第一行包含整数 $n$，表示序列长度。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$，表示序列中的元素。

输出一个由 $n$ 个字符组成的字符串，其中第 $i$ 个字符为： - $\tt 1$，表示下标 $i$ 属于第一类； - $\tt 2$，表示下标 $i$ 属于第二类； - $\tt 3$，表示下标 $i$ 属于第三类。

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson. Nam created a sequence $ a $ consisting of $ n $ ( $ 1