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↕
1794E	Labeling the Tree with Distances data structures dp greedy hashing implementation trees	2400	1.6k
486E	LIS of Sequence data structures dp greedy hashing math	2200	2.7k
79C	Beaver data structures dp greedy hashing strings two pointers	1800	2.1k

Problemset