Problem2613--LIS of Sequence

2613: LIS of Sequence

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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≤105) elements a1,a2,...,an (1≤ai≤105). A subsequence ai1,ai2,...,aik where 1≤i1<i2<...<ik≤n is called increasing if ai1<ai2<ai3<...<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≤i≤n), into three groups:

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

Input

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

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

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.

Examples
Input
1
4
Output
3
Input
4
1 3 2 5
Output
3223
Input
4
1 5 2 3
Output
3133
Note

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

Source/Category

 
[Submit] [Status]