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, that is {a_1, a_3, a_4} = {1, 2, 3}.

Difficulty: interview

Starter code:

Solutions:
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()


n = int(input())
secuencia = [None] * n
ma = 0
for num, e in enumerate(input().strip().split()):
    en = int(e)
    secuencia[num] = [en, 0, num]
    ma = max(ma, en)
escritura = ["1"] * len(secuencia)
# ma = max((x[0] for x in secuencia))
bit = [0] * (ma + 1)

def max_x(x, l):
    suma = 0
    while x != 0:
        suma = max(suma, l[x])
        x -= (x & -x)
    return suma

def update_x(x, l, max_n, val):
    while x <= max_n:
        if val > l[x]:
            l[x] = val
        else:
            return
        x += (x & -x)

# def index_list(item, alist, first=0, last=-1):
#     pos = first
#     while first <= last:
#         midpoint = (first + last) // 2
#         pos = midpoint
#         if alist[midpoint][1] == item:
#             return midpoint
#         else:
#             if item > alist[midpoint][1]:
#                 last = midpoint - 1
#             else:
#                 first = midpoint + 1
#                 pos += 1
#     return pos

def new_get_secuence(e):
    num = secuencia[e][0]
    maximo = max_x(num - 1, bit) + 1
    update_x(num, bit, ma, maximo)
    return maximo

for e in range(n):
    secuencia[e][1] = new_get_secuence(e)

secuencia.sort(key=lambda x: (-x[1], -x[2]))
ultimos = [(ma + 1, 0, n)]
partir = 0
moment_max = secuencia[0][1]
# while moment_max > 0:
#     terminar = n
#     usados = []
#     for e in range(partir, n):
#         if secuencia[e][1] < moment_max:
#             terminar = e
#             break
#         for element in ultimos:
#             if secuencia[e][2] < element[2]:
#                 if secuencia[e][0] < element[0]:
#                     usados.append(secuencia[e])
#                     break
#     if len(usados) == 1:
#         escritura[usados[0][2]] = "3"
#     else:
#         for e in usados:
#             escritura[e[2]] = "2"
#     ultimos = usados
#     partir = terminar
#     moment_max -= 1
usados = []
for e in secuencia:
    if e[1] < moment_max:
        if len(usados) == 1:
            escritura[usados[0][2]] = "3"
        else:
            for y in usados:
                escritura[y[2]] = "2"
        ultimos = usados
        usados = []
        moment_max -= 1
    for element in ultimos:
        if e[2] < element[2]:
            if e[0] < element[0]:
                usados.append(e)
                break
        else:
            break
if len(usados) == 1:
    escritura[usados[0][2]] = "3"
else:
    for y in usados:
        escritura[y[2]] = "2"
print("".join(escritura))






n = int(input())
secuencia = [None] * n
ma = 0
for num, e in enumerate(input().strip().split()):
    en = int(e)
    secuencia[num] = [en, 0, num]
    ma = max(ma, en)
escritura = ["1"] * len(secuencia)
# ma = max((x[0] for x in secuencia))
bit = [0] * (ma + 1)

def max_x(x, l):
    suma = 0
    while x != 0:
        suma = max(suma, l[x])
        x -= (x & -x)
    return suma

def update_x(x, l, max_n, val):
    while x <= max_n:
        if val > l[x]:
            l[x] = val
        else:
            return
        x += (x & -x)

# def index_list(item, alist, first=0, last=-1):
#     pos = first
#     while first <= last:
#         midpoint = (first + last) // 2
#         pos = midpoint
#         if alist[midpoint][1] == item:
#             return midpoint
#         else:
#             if item > alist[midpoint][1]:
#                 last = midpoint - 1
#             else:
#                 first = midpoint + 1
#                 pos += 1
#     return pos

def new_get_secuence(e):
    num = secuencia[e][0]
    maximo = max_x(num - 1, bit) + 1
    update_x(num, bit, ma, maximo)
    return maximo

for e in range(n):
    secuencia[e][1] = new_get_secuence(e)

secuencia.sort(key=lambda x: (-x[1], -x[2]))
ultimos = [(ma + 1, 0, n)]
partir = 0
moment_max = secuencia[0][1]
# while moment_max > 0:
#     terminar = n
#     usados = []
#     for e in range(partir, n):
#         if secuencia[e][1] < moment_max:
#             terminar = e
#             break
#         for element in ultimos:
#             if secuencia[e][2] < element[2]:
#                 if secuencia[e][0] < element[0]:
#                     usados.append(secuencia[e])
#                     break
#     if len(usados) == 1:
#         escritura[usados[0][2]] = "3"
#     else:
#         for e in usados:
#             escritura[e[2]] = "2"
#     ultimos = usados
#     partir = terminar
#     moment_max -= 1
usados = []
for e in secuencia:
    if e[1] < moment_max:
        if len(usados) == 1:
            escritura[usados[0][2]] = "3"
        else:
            for y in usados:
                escritura[y[2]] = "2"
        ultimos = usados
        usados = []
        moment_max -= 1
    for element in ultimos:
        if e[2] < element[2]:
            if e[0] < element[0]:
                usados.append(e)
                break
        else:
            break
if len(usados) == 1:
    escritura[usados[0][2]] = "3"
else:
    for y in usados:
        escritura[y[2]] = "2"
print("".join(escritura))






# a simple parser for python. use get_number() and get_word() to read
def main():
    def parser():
        while 1:
            data = list(input().split(' '))
            for number in data:
                if len(number) > 0:
                    yield(number)

    input_parser = parser()
    gets = lambda: next(input_parser)

    def getNum():
        data = gets()
        try:
            return int(data)
        except ValueError:
            return float(data)
    # ---------program---------
    from bisect import bisect_left
    binslb = bisect_left
    MAXA = int(9e9)
    n = getNum()
    RANGN = range(n)
    a = [ getNum() for _ in RANGN ]

    revlis = []
    g = [MAXA]*n
    for i in reversed(RANGN):
        x = -a[i]
        pt = binslb( g, x )
        revlis.append(pt+1)
        if( x < g[pt] ):
            g[pt] = x
    hlis = max( revlis )

    lis, inlis = [], []
    d = [0]*n
    for i in RANGN: g[i] = MAXA
    for i in RANGN:
        pt = binslb( g, a[i] )
        lis.append( pt+1 )
        inlis.append( lis[i] + revlis[n-i-1] > hlis )
        d[pt] += inlis[-1]
        if( a[i] < g[pt] ):
            g[pt] = a[i]
    
    print( ''.join(
        [ '32'[d[lis[i]-1] > 1] if inlis[i] else '1'  
        for i in RANGN ]
    ) )
        
def __starting_point():
    main()
__starting_point()

# a simple parser for python. use get_number() and get_word() to read
def main():
    def parser():
        while 1:
            data = list(input().split(' '))
            for number in data:
                if len(number) > 0:
                    yield(number)

    input_parser = parser()
    gets = lambda: next(input_parser)

    def getNum():
        data = gets()
        try:
            return int(data)
        except ValueError:
            return float(data)
    # ---------program---------
    from bisect import bisect_left as binsleft
    # bisect_left = bisect_left
    MAXA = int(9e9)
    n = getNum()
    RANGN = range(n)
    a = [ getNum() for _ in RANGN ]

    revlis = []
    g = [MAXA]*n
    for i in reversed(RANGN):
        x = -a[i]
        pt = binsleft( g, x )
        revlis.append(pt+1)
        if( x < g[pt] ):
            g[pt] = x
    hlis = max( revlis )

    lis, inlis = [], []
    d = [0]*n
    for i in RANGN: g[i] = MAXA
    for i in RANGN:
        pt = binsleft( g, a[i] )
        lis.append( pt+1 )
        inlis.append( lis[i] + revlis[n-i-1] > hlis )
        d[pt] += inlis[-1]
        if( a[i] < g[pt] ):
            g[pt] = a[i]
    
    print( ''.join(
        [ '32'[d[lis[i]-1] > 1] if inlis[i] else '1'  
        for i in RANGN ]
    ) )
        
def __starting_point():
    main()
__starting_point()

# a simple parser for python. use get_number() and get_word() to read
def main():
    def parser():
        while 1:
            data = list(input().split(' '))
            for number in data:
                if len(number) > 0:
                    yield(number)

    input_parser = parser()
    gets = lambda: next(input_parser)

    def getNum():
        data = gets()
        try:
            return int(data)
        except ValueError:
            return float(data)
    # ---------program---------
    from bisect import bisect_left as binsleft
    # bisect_left = bisect_left
    MAXA = int(9e9)
    n = getNum()
    RANGN = range(n)
    a = [ getNum() for _ in RANGN ]

    revlis = []
    g = [MAXA]*n
    for i in reversed(RANGN):
        x = -a[i]
        pt = binsleft( g, x )
        revlis.append(pt+1)
        if( x < g[pt] ):
            g[pt] = x
    hlis = max( revlis )

    lis, inlis = [], []
    d = [0]*n
    for i in RANGN: g[i] = MAXA
    for i in RANGN:
        pt = binsleft( g, a[i] )
        lis.append( pt+1 )
        inlis.append( lis[i] + revlis[n-i-1] > hlis )
        d[pt] += inlis[-1]
        if( a[i] < g[pt] ):
            g[pt] = a[i]
    
    print( ''.join(
        [ '32'[d[lis[i]-1] > 1] if inlis[i] else '1'  
        for i in RANGN ]
    ) )
        
def __starting_point():
    main()
__starting_point()

# a simple parser for python. use get_number() and get_word() to read
def main():
    def parser():
        while 1:
            data = list(input().split(' '))
            for number in data:
                if len(number) > 0:
                    yield(number)

    input_parser = parser()
    gets = lambda: next(input_parser)

    def getNum():
        data = gets()
        try:
            return int(data)
        except ValueError:
            return float(data)
    # ---------program---------
    from bisect import bisect_left # as bisect_left
    MAXA = int(9e9)
    n = getNum()
    RANGN = range(n)
    a = [ getNum() for _ in RANGN ]

    revlis = []
    g = [MAXA]*n
    for i in reversed(RANGN):
        x = -a[i]
        pt = bisect_left( g, x )
        revlis.append(pt+1)
        if( x < g[pt] ):
            g[pt] = x
    hlis = max( revlis )

    lis, inlis = [], []
    d = [0]*n
    for i in RANGN: g[i] = MAXA
    for i in RANGN:
        pt = bisect_left( g, a[i] )
        lis.append( pt+1 )
        inlis.append( lis[i] + revlis[n-i-1] > hlis )
        d[pt] += inlis[-1]
        if( a[i] < g[pt] ):
            g[pt] = a[i]
    
    print( ''.join(
        [ '32'[d[lis[i]-1] > 1] if inlis[i] else '1'  
        for i in RANGN ]
    ) )
        
def __starting_point():
    main()
__starting_point()

# http://codeforces.com/problemset/problem/486/E
import sys
import re
import collections
import threading
import bisect # bisect.bisect(list, value)

N = 0

Last = []
AA = [0 for _ in range(100005)]
LL = [0 for _ in range(100005)]
BB = [0 for _ in range(100005)] # reverse
SS = [0 for _ in range(100005)] # reverse
TT = [0 for _ in range(100005)] # reverse
ANS = [1 for _ in range(100005)]


def LIS(A, L):
    nonlocal N

    Last.append(-1) # dummy

    for i in range(N):
        if Last[-1] < A[i]:
            Last.append(A[i])

        it = bisect.bisect_left(Last, A[i]) # lower_bound() in C++

        Last[it] = A[i]
        L[i] = it

N = int(sys.stdin.readline())
AA = list(map(int, sys.stdin.readline().strip().split()))

LIS(AA, LL)

length = max(LL)

for i in range(N):
    BB[N-i-1] = 1000000 - AA[i]

Last = []

LIS(BB, SS)

for i in range(N):
    TT[N-i-1] = SS[i]

for i in range(N):
    if LL[i] + TT[i] == length + 1 :
        ANS[i] = 3

maxi = 0;
mini = 1000000;

for i in range(N):
    if ANS[i] != 1:
        if AA[i] <= maxi: ANS[i] = 2
        maxi = max(maxi, AA[i])

for i in range(N-1, -1, -1):
    if ANS[i] != 1:
        if AA[i] >= mini: ANS[i] = 2
        mini = min(mini, AA[i])

for i in range(N):
    print(ANS[i], end="", flush=True)

print()