Алиса перепутала слова трансмутация и перестановка! У неё есть массив \(a\), заданный тремя целыми числами \(n\), \(b\), \(c\): массив \(a\) имеет длину \(n\) и задаётся по правилу \(a_i = b\cdot (i - 1) + c\) для \(1\le i\le n\). Например, если \(n=3\), \(b=2\) и \(c=1\), то \(a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]\).
Алисе очень нравятся перестановки \([0, \ldots, n-1]\)\(^{\text{∗}}\) и она хотела бы преобразовать \(a\) в перестановку. В одной операции Алиса заменяет максимальный элемент массива \(a\) на \(\operatorname{MEX}\)\(^{\text{†}}\) массива \(a\). Если в массиве \(a\) несколько максимальных элементов, Алиса выбирает самый левый для замены.
Можете ли вы помочь Алисе выяснить, сколько операций ей нужно выполнить, чтобы \(a\) впервые стал перестановкой? Если это невозможно, вы должны сообщить об этом.
Выходные данные
Для каждого набора входных данных, если массив никогда не сможет стать перестановкой, выведите одно целое число \(-1\). В противном случае выведите минимальное количество операций, необходимых для того, чтобы массив стал перестановкой.
Примечание
В первом наборе входных данных массив уже \([0, 1, \ldots, 9]\), поэтому операции не требуются.
В третьем наборе входных данных начальный массив равен \([1, 3, 5, \ldots, 199]\). После первой операции \(199\) преобразуется в \(0\). Во второй операции \(197\) преобразуется в \(2\). Если продолжать, потребуется ровно \(50\) операций, чтобы получить массив \([0, 1, 2, 3, \ldots, 99]\).
В четвертом наборе входных данных требуется две операции: \([1,1,1] \to [0,1,1] \to [0,2,1]\).
В пятом наборе входных данных процесс выглядит следующим образом: \([0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]\). Этот процесс повторяется бесконечно, поэтому массив никогда не становится перестановкой, и ответ равен \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
10 1 0
1 2 3
100 2 1
3 0 1
3 0 0
1000000000000000000 0 0
1000000000000000000 1000000000000000000 1000000000000000000
|
0
1
50
2
-1
-1
1000000000000000000
|