В ряд выстроены \(n\) студентов. Два тренера набирают две команды — первый тренер выбирает первую команду, а второй тренер выбирает вторую команду.
Умение программировать \(i\)-го студента равно целому числу \(a_i\). Все умения программировать различны и лежат в отрезке от \(1\) до \(n\).
Сначала первый тренер выбирает себе студента с максимальным умением программировать среди всех студентов, не взятых в какую-либо команду, а также \(k\) студентов, стоящих ближе всего слева от него и \(k\) студентов, стоящих ближе всего справа от него (если слева или справа стоит меньше, чем \(k\) студентов, все они будут взяты). Все выбранные студенты покидают ряд и присоединяются к первой команде. Затем второй тренер делает такой же ход (но все студенты, выбранные им, присоединяются ко второй команде). Затем опять первый тренер делает такой же ход, и так далее. Это продолжается до тех пор, пока есть хотя бы один студент, стоящий в ряду.
Ваша задача — определить, какие студенты будут взяты в первую команду, а какие будут взяты во вторую команду.
Выходные данные
Выведите строку, состоящую из \(n\) символов; \(i\)-й символ должен быть равен 1, если \(i\)-й студент присоединится к первой команде и 2 в ином случае.
Примечание
В первом тестовом примере первый тренер выберет студента на позиции \(3\) и ряд станет пустым (все студенты пойдут в первую команду).
Во втором тестовом примере первый тренер выберет студента на позиции \(4\) и ряд превратится в \([2, 1]\) (студенты с умениями программировать \([3, 4, 5]\) пойдут в первую команду). Затем второй тренер выберет студента на позиции \(1\) и ряд станет пустым (и студенты с умениями программировать \([1, 2]\) пойдут во вторую команду).
В третьем тестовом примере первый тренер выберет студента на позиции \(1\) и ряд превратится в \([1, 3, 5, 4, 6]\) (студенты с умениями программировать \([2, 7]\) пойдут в первую команду). Затем второй тренер выберет студента на позиции \(5\) и ряд превратится в \([1, 3, 5]\) (студенты с умениями программировать \([4, 6]\) пойдут во вторую команду). Затем первый тренер выберет студента на позиции \(3\) и ряд превратится в \([1]\) (студенты с умениями программировать \([3, 5]\) пойдут в первую команду). И затем второй тренер выберет оставшегося студента (и студент с умением программировать \(1\) пойдет во вторую команду).
В четвертом тестовом примере первый тренер выберет студента на позиции \(3\) и ряд превратится в \([2, 1]\) (студенты с умениями программировать \([3, 4, 5]\) пойдут в первую команду). Затем второй тренер выберет студента на позиции \(1\) и ряд станет пустым (и студенты с умениями программировать \([1, 2]\) пойдут во вторую команду).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2 4 5 3 1
|
11111
|
|
2
|
5 1
2 1 3 5 4
|
22111
|
|
3
|
7 1
7 2 1 3 5 4 6
|
1121122
|
|
4
|
5 1
2 4 5 3 1
|
21112
|