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:
-
group of all i such that ai belongs to no longest increasing subsequences.
-
group of all i such that ai belongs to at least one but not every longest increasing subsequence.
-
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.
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.
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}.