human
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?

 Can you provide a Python program to print a string consisting of n characters?
assistant
#Here is Python program to print a string consisting of n characters.

# 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()