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:

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.

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.

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, that is ${*a*_{1}, *a*_{3}, *a*_{4}}$ = ${1, 2, 3}$.