A9747 | 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<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<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 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_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<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.

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.