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 \le n \le 105) elements a1,a2,...,an (1 \le ai \le 105). A subsequence ai1,ai2,...,aik where 1 \le i1 \lt i2 \lt ... \lt ik \le n is called increasing if ai1 \lt ai2 \lt ai3 \lt ... \lt aik. 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 \le i \le n), into three groups:
group of all i such that ai belongs to no longest increasing subsequences. group of all i such that ai belongs to at least one but not every longest increasing subsequence. group of all i such that ai 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.

The first line contains the single integer n (1 \le n \le 105) denoting the number of elements of sequence a.

The second line contains n space-separated integers a1,a2,...,an (1 \le ai \le 105).

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.

In the second sample, sequence a consists of 4 elements: {a1,a2,a3,a4} = {1,3,2,5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a1,a2,a4} = {1,3,5} and {a1,a3,a4} = {1,2,5}.

In the third sample, sequence a consists of 4 elements: {a1,a2,a3,a4} = {1,5,2,3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a1,a3,a4} = {1,2,3}.