下一课“数据结构与算法”将讨论序列的最长递增子序列(简称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}。