Вам дан массив \(a_1, a_2, \ldots, a_n\). Вам нужно найти такой массив \(b_1, b_2, \ldots, b_n\), который состоит из чисел \(1\), \(2\), \(3\), и для него выполняются ровно два из следующих трёх условий:
- Существуют такие индексы \(1 \leq i, j \leq n\), для которых \(a_i = a_j\), \(b_i = 1\), \(b_j = 2\).
- Существуют такие индексы \(1 \leq i, j \leq n\), для которых \(a_i = a_j\), \(b_i = 1\), \(b_j = 3\).
- Существуют такие индексы \(1 \leq i, j \leq n\), для которых \(a_i = a_j\), \(b_i = 2\), \(b_j = 3\).
Если подходящего массива не существует, вы должны сообщить об этом.
Выходные данные
Для каждого набора входных данных выведите -1, если ответа не существует. Иначе выведите \(b_1, b_2, \ldots, b_n\) — массив, состоящий из чисел \(1\), \(2\), \(3\) и подходящий под ровно два условия из трёх перечисленных. Если ответов несколько, вы можете вывести любой из них.
Примечание
В первом наборе входных данных \(b = [1, 2, 3, 1, 1, 1]\) подходит под условие \(1\) так как при \(i = 4\), \(j = 2\): \(a_i = a_j\), \(b_i = 1\), \(b_j = 2\). Подходит под условие \(2\) так как при \(i = 6\), \(j = 3\): \(a_i = a_j\), \(b_i = 1\), \(b_j = 3\), и не подходит под условие \(3\). Итого выполнено ровно два условия из трёх.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69
|
1 2 3 1 1 1
-1
3 2 2 1
-1
2 1 2 1 3
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2
|