Вам дан неубывающий массив, состоящий из неотрицательных целых чисел \(a_1, a_2, \ldots, a_n\). Также вам дано положительное целое число \(k\).
Вы хотите найти \(m\) неубывающих массивов, состоящих из неотрицательных целых чисел \(b_1, b_2, \ldots, b_m\), таких что:
- размер \(b_i\) равен \(n\) для всех \(1 \leq i \leq m\);
- для всех \(1 \leq j \leq n\), \(a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}\). Другими словами, массив \(a\) равен поэлементной сумме массивов \(b_i\);
- количество различных элементов массива \(b_i\) не превосходит \(k\) для всех \(1 \leq i \leq m\).
Найдите минимальное возможное значение \(m\) или сообщите, что ни одного возможного значения \(m\) не существует.
Выходные данные
Для каждого набора входных данных выведите единственное целое число: минимальное возможное значение \(m\). Если таких \(m\) не существует, выведите \(-1\).
Примечание
В первом наборе входных данных не существует ни одного возможного значения \(m\), потому что все элементы всех массивов должны будут быть равными \(0\). Но в этом случае невозможно получить \(a_4 = 1\) как сумму нескольких нулей.
Во втором наборе входных данных мы можем взять \(b_1 = [3, 3, 3]\). \(1\) — это минимальное возможное значение \(m\).
В третьем наборе входных данных мы можем взять \(b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]\) и \(b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]\). Легко заметить, что \(a_i = b_{1, i} + b_{2, i}\) для всех \(i\) и количество различных элементов в каждом из массивов \(b_1\) и \(b_2\) равно \(3\) (что не превосходит \(3\)). Можно доказать, что \(2\) — это минимальное возможное значение \(m\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 1
0 0 0 1
3 1
3 3 3
11 3
0 1 2 2 3 3 3 4 4 4 4
5 3
1 2 3 4 5
9 4
2 2 3 5 7 11 13 13 17
10 7
0 1 1 2 3 3 4 5 5 6
|
-1
1
2
2
2
1
|