CF486E.LIS of Sequence

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 ≤ n ≤ 105) elements _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105). A subsequence _a__i_1, _a__i_2, ..., a__i__k where 1 ≤ _i_1 < _i_2 < ... < i__k ≤ n is called increasing if _a__i_1 < _a__i_2 < _a__i_3 < ... < a__i__k. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups:

1. group of all i such that a__i belongs to no longest increasing subsequences.
2. group of all i such that a__i belongs to at least one but not every longest increasing subsequence.
3. group of all i such that a__i belongs to every longest increasing subsequence.

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.

下一节“数据结构与算法”课程将讲解序列的最长递增子序列（简称 LIS）。为了更好地理解该内容，Nam 决定在正式上课前几天提前学习。

Nam 构造了一个由 $ n $（$ 1 \leq n \leq 10^5 $）个元素 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^5 $）组成的序列 $ a $。若下标满足 $ 1 \leq i_1 < i_2 < \dots < i_k \leq n $，则子序列 $ a_{i_1}, a_{i_2}, \dots, a_{i_k} $ 称为递增的，当且仅当 $ a_{i_1} < a_{i_2} < a_{i_3} < \dots < a_{i_k} $。在所有递增子序列中，长度最大的称为最长递增子序列。

Nam 意识到一个序列可能拥有多个最长递增子序列。因此，他将所有下标 $ i $（$ 1 \leq i \leq n $）划分为以下三类：

1. 所有满足 $ a_i $ 不属于任意一个最长递增子序列的下标 $ i $；
2. 所有满足 $ a_i $ 至少属于某一个、但不属於全部最长递增子序列的下标 $ i $；
3. 所有满足 $ a_i $ 属于每一个最长递增子序列的下标 $ i $。

由于序列 $ a $ 的最长递增子序列数量可能非常大，上述分类过程十分困难。你的任务是帮助 Nam 完成这项工作。

The first line contains the single integer n (1 ≤ n ≤ 105) denoting the number of elements of sequence a.

The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示序列 $a$ 的元素个数。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^5$）。

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.

输出一个由 n 个字符组成的字符串。第 i 个字符应为 '1'、'2' 或 '3'，具体取决于索引 i 属于上述所列的哪个组。

In the second sample, sequence a consists of 4 elements: {_a_1, _a_2, _a_3, _a_4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {_a_1, _a_2, _a_4} = {1, 3, 5} and {_a_1, _a_3, _a_4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {_a_1, _a_2, _a_3, _a_4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {_a_1, _a_3, _a_4} = {1, 2, 3}.

在第二个样例中，序列 $a$ 包含 4 个元素：$\{a_1,\,a_2,\,a_3,\,a_4\} = \{1,\,3,\,2,\,5\}$。序列 $a$ 恰好有 2 个长度为 3 的最长递增子序列，它们分别是 $\{a_1,\,a_2,\,a_4\} = \{1,\,3,\,5\}$ 和 $\{a_1,\,a_3,\,a_4\} = \{1,\,2,\,5\}$。

在第三个样例中，序列 $a$ 包含 4 个元素：$\{a_1,\,a_2,\,a_3,\,a_4\} = \{1,\,5,\,2,\,3\}$。序列 $a$ 恰好有 1 个长度为 3 的最长递增子序列，即 $\{a_1,\,a_3,\,a_4\} = \{1,\,2,\,3\}$。