Маленький Пол хочет научиться играть на фортепиано. Он уже нашёл мелодию, которую будет играть. Для простоты он выписал последовательность \(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\), а не \(=\).
Найдите любую удобную аппликатуру или скажите, что таких нет.
Выходные данные
Если удобных аппликатур к этой мелодии не существует, выведите \(-1\). В противном случае выведите \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) от \(1\) до \(5\), задающих удобную аппликатуру.