E. Dreamoon любит AA
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть строка длины $$$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