LIS of Sequence

2000ms

262144K

Description:

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⁵) elements a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵). A subsequence a_i₁, a_i₂, ..., a_{i_k} where 1 ≤ i₁ < i₂ < ... < i_k ≤ n is called increasing if a_i₁ < a_i₂ < a_i₃ < ... < 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⁵) denoting the number of elements of sequence a.

The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵).

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.

Sample Input:

1
4

Sample Output:

Sample Input:

4
1 3 2 5

Sample Output:

Sample Input:

4
1 5 2 3

Sample Output:

Note:

In the second sample, sequence a consists of 4 elements: {a₁, a₂, a₃, a₄} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a₁, a₂, a₄} = {1, 3, 5} and {a₁, a₃, a₄} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a₁, a₂, a₃, a₄} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a₁, a₃, a₄} = {1, 2, 3}.

Informação

Provedor Codeforces

Código CF486E