E. Наибольшие возрастающие подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Следующее занятие по структурам данных и алгоритмам будет посвящено наибольшей возрастающей подпоследовательности. Чтобы лучше разобраться в теме, Нам решил начать готовиться за несколько дней до занятия.

Нам записал последовательность a, состоящую из n (1 ≤ n ≤ 105) элементов a1, a2, ..., an (1 ≤ ai ≤ 105). Подпоследовательность ai1, ai2, ..., aik, где 1 ≤ i1 < i2 < ... < ik ≤ n называется возрастающей, если ai1 < ai2 < ai3 < ... < aik. Возрастающая подпоследовательность называется наибольшей, если она обладает максимальной длиной среди всех возрастающих подпоследовательностей.

Нам понимает, что у последовательности может быть несколько наибольших возрастающих подпоследовательностей. В связи с этим он хочет разделить все индексы i (1 ≤ i ≤ n) на три группы:

  1. группа всех i, таких, что ai не является элементом ни одной наибольшей возрастающей подпоследовательности.
  2. группа всех i, таких, что ai является элементом по крайней мере одной, но не каждой наибольшей возрастающей подпоследовательности.
  3. группа всех i, таких, что ai является элементом каждой наибольшей возрастающей подпоследовательности.

Так как количество наибольших возрастающей подпоследовательностей a может быть очень большим, произвести подобное разделение очень непросто. Ваша задача — помочь Наму справиться с этим.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 105), обозначающее количество элементов последовательности a.

Во второй строке записано n целых чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 105).

Выходные данные

Выведите строку, состоящую из n символов. i-й символ должен равняться «1», «2» или «3» в зависимости от того, к какой группе из вышеперечисленных принадлежит индекс i.

Примеры
Входные данные
1
4
Выходные данные
3
Входные данные
4
1 3 2 5
Выходные данные
3223
Входные данные
4
1 5 2 3
Выходные данные
3133
Примечание

Во втором примере последовательность a состоит из 4 элементов: {a1, a2, a3, a4} = {1, 3, 2, 5}. В последовательности a есть ровно 2 наибольшие возрастающие подпоследовательности длины 3, а именно: {a1, a2, a4} = {1, 3, 5} и {a1, a3, a4} = {1, 2, 5}.

В третьем примере последовательность a состоит из 4 элементов: {a1, a2, a3, a4} = {1, 5, 2, 3}. В последовательности a есть ровно 1 наибольшая возрастающая подпоследовательность длины 3, а именно {a1, a3, a4} = {1, 2, 3}.