У вас есть гирлянда, состоящая из \(4\) цветных лампочек, цвет \(i\)-й лампочки — \(s_i\).
Изначально все лампочки выключены. Ваша задача — включить все лампочки. Вы можете выполнять следующую операцию любое количество раз: выбрать лампочку и переключить ее состояние (включить, если была выключена, и выключить, если была включена). Единственное ограничение на вышеописанную операцию — вы можете применять операцию к лампочке, только если предыдущая операция была применена к лампочке другого цвета (первую операцию можно применять к любой лампочке).
Посчитайте минимальное количество операций, чтобы включить все лампочки, или сообщите, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, чтобы включить все лампочки. Если включить все лампочки невозможно, выведите -1.
Примечание
В первом примере все цвета различные, значит, мы можем просто включить все лампочки за \(4\) операции.
Во втором примере невозможно включить все лампочки, т.к. после включения одной лампочки включить другие невозможно.
В третьем примере можно действовать следующим образом: включить первую лампочку, включить третью лампочку, включить четвертую лампочку, выключить третью лампочку, включить вторую лампочку, включить третью лампочку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9546
0000
3313
|
4
-1
6
|