题目描述

给你一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，你需要把这 $n$ 个元素分成三类：

1. 所有的最长上升子序列都不包含这个元素。
2. 有但非所有的最长上升子序列包含这个元素。
3. 所有的最长上升子序列都包含这个元素。

输入格式

第一行包含一个正整数 $n$，表示序列的长度，$1 \le n \le 10^5$。

第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$，表示序列中的元素，$1 \le a_i \le 10^5$。

输出格式

一行，包含一个长度为 $n$ 的、由 $1,2,3$ 三种数字组成的字符串，第 $i$ 个数字表示 $a_i$ 所属类别。

1
4

3

4
1 3 2 5

3223

4
1 5 2 3

3133