I found an interesting problem on https://codeforces.com/problemset/problem/486/E:
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^5) elements a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). A subsequence a_{i}_1, a_{i}_2, ..., a_{i}_{k} where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n is called increasing if a_{i}_1 < a_{i}_2 < a_{i}_3 < ... < 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^5) denoting the number of elements of sequence a.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----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: {a_1, a_2, a_3, a_4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a_1, a_2, a_4} = {1, 3, 5} and {a_1, a_3, a_4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3,...

I tried it in Python, but could not do it. Can you solve it?
N = int( input() )
A = list( map( int, input().split() ) )

maxa = max( A )

def upd( ftree, x, v ):
  while x <= maxa:
    ftree[ x ] = max( ftree[ x ], v )
    x += x & -x

def qry( ftree, x ):
  res = 0
  while x:
    res = max( res, ftree[ x ] )
    x -= x & -x
  return res

st_len = [ 0 for i in range( N ) ]
ftree = [ 0 for i in range( maxa + 1 ) ]
for i in range( N - 1, -1, -1 ):
  st_len[ i ] = qry( ftree, maxa + 1 - A[ i ] - 1 ) + 1
  upd( ftree, maxa + 1 - A[ i ], st_len[ i ] )

ed_len = [ 0 for i in range( N ) ]
ftree = [ 0 for i in range( maxa + 1 ) ]
for i in range( N ):
  ed_len[ i ] = qry( ftree, A[ i ] - 1 ) + 1
  upd( ftree, A[ i ], ed_len[ i ] )

max_len = max( st_len )
st_cnt_len = [ 0 for i in range( N + 1 ) ]
for i in range( N ):
  if ed_len[ i ] + st_len[ i ] - 1 == max_len:
    st_cnt_len[ st_len[ i ] ] += 1

for i in range( N ):
  if ed_len[ i ] + st_len[ i ] - 1 != max_len:
    print( 1, end = "" )
  elif st_cnt_len[ st_len[ i ] ] > 1:
    print( 2, end = "" )
  else:
    print( 3, end = "" )
print()