Это сложная версия задачи. Единственное отличие между простой и сложной версиями — ограничения на \(n\), \(k\), \(a_i\) и сумму \(n\) по всем наборам входных данных. Вы можете делать взломы, только если обе версии задачи решены.
Обратите внимание на нестандартное ограничение по памяти.
Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\) длины \(n\) и целое число \(k\).
Стоимость массива целых чисел \(p_1, p_2, \ldots, p_n\) длины \(n\) равна \(\)\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).\(\)
Здесь \(\lfloor \frac{x}{y} \rfloor\) обозначает целую часть от деления \(x\) на \(y\). Найдите минимальную возможную стоимость массива \(p\), такого что \(1 \le p_i \le k\) для всех \(1 \le i \le n\).
Выходные данные
Для каждого набора входных данных выведите одно число: минимальную возможную стоимость массива \(p\), удовлетворяющего требованию выше.
Примечание
В первом наборе входных данных оптимальный массив \(p = [1, 1, 1, 2, 2]\). Массив значений \(\lfloor \frac{a_i}{p_i} \rfloor\) для данного массива равен \([4, 5, 6, 4, 5]\). Стоимость \(p\) равна \(\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2\). Можно показать, что не существует массива (удовлетворяющего требованию из условия) с меньшей стоимостью.
Во втором наборе входных данных один из оптимальных массивов \(p = [12, 12, 12, 12, 12]\). Все значения \(\lfloor \frac{a_i}{p_i} \rfloor\) для данного массива равны \(0\).
В третьем наборе входных данных единственный возможный массив \(p = [1, 1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
|
2
0
13
1
4
7
0
|