C. Игра на фортепиано
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Пол хочет научиться играть на фортепиано. Он уже нашёл мелодию, которую будет играть. Для простоты он выписал последовательность $$$a_1, a_2, \ldots, a_n$$$ целых чисел, которые означают номер клавиш: чем больше номер, тем правее клавиша на клавиатуре.

Пол очень умный и понимает, что самое важное — правильная аппликатура, то есть, правильно выбрать, каким пальцем какую ноту играть. Если выбрать неудобные пальцы, то потом можно потратить уйму времени на попытки научиться играть мелодию и всё равно в итоге не преуспеть.

Обозначим пальцы на руке числами от $$$1$$$ до $$$5$$$. Назовём аппликатурой любую последовательность $$$b_1, \ldots, b_n$$$ номеров пальцев. Назовём аппликатуру удобной, если для любого $$$1\leq i \leq n - 1$$$ выполнено следующее:

  • если $$$a_i < a_{i+1}$$$, то $$$b_i < b_{i+1}$$$, потому что иначе придётся оторвать руку от клавиатуры, чтобы сыграть $$$(i+1)$$$-ю ноту;
  • если $$$a_i > a_{i+1}$$$, то $$$b_i > b_{i+1}$$$ по той же причине;
  • если $$$a_i = a_{i+1}$$$, то $$$b_i\neq b_{i+1}$$$, потому что довольно нелепо использовать один и тот же палец два раза подряд. Обратите внимание, что между $$$b_i$$$ и $$$b_{i+1}$$$ стоит знак $$$\neq$$$, а не $$$=$$$.

Найдите любую удобную аппликатуру или скажите, что таких нет.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$), обозначающее число нот в мелодии.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) — номера этих нот.

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

Если удобных аппликатур к этой мелодии не существует, выведите $$$-1$$$. В противном случае выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ от $$$1$$$ до $$$5$$$, задающих удобную аппликатуру.

Примеры
Входные данные
5
1 1 4 2 2
Выходные данные
1 4 5 4 5 
Входные данные
7
1 5 7 8 10 3 1
Выходные данные
1 2 3 4 5 4 3 
Входные данные
19
3 3 7 9 8 8 8 8 7 7 7 7 5 3 3 3 3 8 8
Выходные данные
1 3 4 5 4 5 4 5 4 5 4 5 4 3 5 4 3 5 4 
Примечание

Третий тест из условия — что-то вроде песни "Нон стоп" группы Рефлекс.