Однажды шушанчики нашли последовательность из n целых чисел, записанную на доске. Шушанчики умеют выполнять с ней одну операцию, которая состоит из двух шагов:
- Дописать в конец последовательности число, равное k-му от начала числу в текущей последовательности;
- Стереть первое число текущей последовательности.
Шушанчиков очень заинтересовал вопрос: через сколько операций все числа на доске станут одинаковыми, и станут ли они одинаковыми когда-нибудь вообще.
Выходные данные
Выведите минимальное число операций, требуемых, чтобы все числа на доске стали одинаковыми, или -1, если этого невозможно добиться.
Примечание
В первом тестовом примере после первой операции на доске будет записана последовательность [1, 1, 1]. Значит одной операции достаточно, чтобы все числа стали одинаковые. Таким образом ответ равен единице.
Во втором тестовом примере последовательность никогда не будет состоять из одинаковых чисел. В ней всегда будут содержаться как минимум два различных числа 3 и 1. Таким образом ответ равен -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
3 1 1
|
1
|
|
2
|
3 1
3 1 1
|
-1
|