Есть строка длины $$$n+1$$$ из символов 'A' и 'B'. Первый и последний символ в этой строке равны 'A'.
Вам таже дано $$$m$$$ индексов $$$p_1, p_2, \ldots, p_m$$$ (в $$$0$$$-индексации), описывающих другие позиции символов 'A' в строке.
Обозначим минимальное расстояние между соседними буквами 'A' за $$$l$$$, а максимальное расстояние между соседними 'A' за $$$r$$$.
Например, $$$(l,r)$$$ строки "ABBAABBBA" равно $$$(1,4)$$$.
Обозначим за степень баланса строки величину $$$r-l$$$.
Теперь Dreamoon хочет изменить ровно $$$k$$$ символов 'B' на 'A', и он хочет сделать степень баланса строки как можно меньше.
Пожалуйста, найдите минимальное возможное значение степени баланса.
В первой строке записано одно целое число $$$t$$$, содержащее количество наборов входных данных ($$$1 \leq t \leq 400\,000$$$).
В каждом наборе входных данных, первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^{15}, 0 \leq m \leq 400\,000, 0 \leq k < n - m$$$).
Во второй строке записаны $$$m$$$ целых чисел $$$p_1, p_2, \ldots, p_m$$$, ($$$0 < p_1 < p_2 < \ldots < p_m < n$$$).
Сумма по всем $$$m$$$ не превосходит $$$400\,000$$$.
Для каждого набора входных данных, выведите одно целое число: минимальное возможное значение степени баланса после $$$k$$$ изменений 'B' на 'A'.
5 80 3 5 11 24 50 81 7 12 4 10 17 26 37 48 61 25 10 14 3 4 7 12 13 15 17 19 21 23 1 0 0 10 2 0 2 4
5 2 0 0 4
Название |
---|