← 返回题目列表

Codeforces · 486/E

E. 序列 LIS

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

下一课“数据结构与算法”将讨论序列的最长递增子序列(简称LIS)。为了更好地理解,Nam决定在课前几天学习它。

Nam 创建了一个由 n (1 ≤ n ≤ 105) 个元素 a1, a2, ..., an (1 ≤ ai ≤ 105) 组成的序列 a。如果 ai1 < ai2 < ai3 < ... < aik,则子序列 ai1, ai2, ..., aik 称为递增子序列,其中 1 ≤ i1 < i2 < ... < ik ≤ n。如果一个递增子序列在所有递增子序列中具有最大长度,则该递增子序列被称为最长。

Nam 意识到一个序列可能有几个最长的递增子序列。因此,他将所有索引 i (1 ≤ i ≤ n) 分为三组:

1. 所有 i 组成的组,使得 ai 不属于最长递增子序列。
2. 所有 i 组成的组,使得 ai 属于至少一个但不是每个最长递增子序列。
3. 所有 i 的组,使得 ai 属于每个最长递增子序列。

由于a的最长递增子序列的数量可能非常大,因此分类过程非常困难。你的任务就是帮助他完成这项工作。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105),表示序列 a 的元素数量。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 105)。

输出

打印由 n 个字符组成的字符串。第 i 个字符应该是“1”、“2”或“3”,具体取决于上面列出的索引 i 属于哪个组。

示例

输入 #1

1
4

输出 #1

3

输入 #2

4
1 3 2 5

输出 #2

3223

输入 #3

4
1 5 2 3

输出 #3

3133

注意

在第二个示例中,序列 a 由 4 个元素组成:{a1, a2, a3, a4} = {1, 3, 2, 5}。序列 a 恰好有 2 个长度为 3 的最长递增子序列,它们是 {a1, a2, a4} = {1, 3, 5} 和 {a1, a3, a4} = {1, 2, 5}。

在第三个示例中,序列 a 由 4 个元素组成:{a1, a2, a3, a4} = {1, 5, 2, 3}。序列a正好有1个长度为3的最长递增子序列,即{a1, a3, a4} = {1, 2, 3}。