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_i1, a_i2, ..., a_ik where 1 ≤ i₁ < i₂ < ... < i_k ≤ n is called increasing if a_i1 < a_i2 < a_i3 < ... < a_ik. 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 a_i belongs to no longest increasing subsequences.
2. group of all i such that a_i belongs to at least one but not every longest increasing subsequence.
3. 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.

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⁵).

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.