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 ≤ 10⁵) elements a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵). A subsequence a_i₁, a_i₂, ..., a_{i_k} where 1 ≤ i₁ < i₂ < ... < i_k ≤ n is called increasing if a_i₁ < a_i₂ < a_i₃ < ... < 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:

group of all i such that a_i belongs to no longest increasing subsequences.
group of all i such that a_i belongs to at least one but not every longest increasing subsequence.
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.

Input

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

The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵).

Output

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.

Note

In the second sample, sequence a consists of 4 elements: {a₁, a₂, a₃, a₄} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a₁, a₂, a₄} = {1, 3, 5} and {a₁, a₃, a₄} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a₁, a₂, a₃, a₄} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a₁, a₃, a₄} = {1, 2, 3}.

✓	#	Name		✎	Rating↕	Solved↕
	1980E	Permutation of Rows and Columns constructive algorithms data structures greedy hashing implementation math matrices sortings			1600	13.3k
	486E	LIS of Sequence data structures dp greedy hashing math			2200	2.7k

Problemset