486_E. LIS of Sequence
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}.
```python
# 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 ]
    ) )
        
if __name__ == "__main__":
    main()
```