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}.

Idx	Name	Rating
A	Calculating Function	800
B	OR in Matrix	1300
C	Palindrome Transformation	1700
D	Valid Sets	2100
E	LIS of Sequence	2200

Codeforces Round 277 (Div. 2)