Dreamoon Loves AA
Contest: Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!
Difficulty rating: 3300
Tags: binary search, greedy

There is a string of length $$$n+1$$$ of characters 'A' and 'B'. The first character and last character of the string are equal to 'A'.

You are given $$$m$$$ indices $$$p_1, p_2, \ldots, p_m$$$ ($$$0$$$-indexation) denoting the other indices of characters 'A' in the string.

Let's denote the minimum distance between two neighboring 'A' as $$$l$$$, and maximum distance between neighboring 'A' as $$$r$$$.

For example, $$$(l,r)$$$ of string "ABBAABBBA" is $$$(1,4)$$$.

And let's denote the balance degree of a string as the value of $$$r-l$$$.

Now Dreamoon wants to change exactly $$$k$$$ characters from 'B' to 'A', and he wants to make the balance degree of the string as small as possible.

Please calculate the required minimum possible value of balance degree.

Input format:
The first line contains one integer $$$t$$$ denoting the number of test cases ($$$1 \leq t \leq 400\,000$$$).

For each test case, the first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{15}, 0 \leq m \leq 400\,000, 0 \leq k < n - m$$$).

The second line contains $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$, ($$$0 < p_1 < p_2 < \ldots < p_m < n$$$).

The total sum of $$$m$$$ is at most $$$400\,000$$$.

Output format:
For each test case, print one integer: the smallest possible value of balance degree after $$$k$$$ changes of 'B' to 'A'.

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

Example input:
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

Example output:
5
2
0
0
4

Editorial:
The idea of this problem comes to my brain when I recall that I'm cooking and I want to cut a carrot into many pieces and make the size of each piece as evenly as possible. I think this problem is very interesting. So that's why I determine to prepare a Codeforces contest after so many years. I hope I can share this problem with as many people as possible.
There are some methods to solve this problem. I only show the most beautiful one below. This method is given by isaf27 (And most AC users solve it with this method. I admire them very much).
Firstly, we translate the problem into a more convenient model.
Let $$$p_{m+1} = n$$$, $$$a_i = p_i - p_{i-1}$$$ ($$$1 \le i \le m+1$$$), $$$M = m + 1$$$, and $$$K = m + 1 + k$$$. Then the problem is equivalent to we want to do integer partition on $$$M$$$ integers $$$a_1, a_2, \ldots, a_M$$$, such that $$$a_i$$$ is divided into $$$d_i$$$ positive integers where $$$\sum d_i = K$$$. Our target is to minimize the difference between the largest integer and smallest integer after division.
An important observation is, we always can achieve our target by making the difference of the largest integer and the smallest integer that is divided from the same integer is at most one. So our target is minimizing $$$\max_{1 \le i \le M}\limits{(\left\lceil \frac{a_i}{d_i} \right \rceil)} - \min_{1 \le i \le M}\limits{(\left\lfloor \frac{a_i}{d_i} \right \rfloor)}$$$ where $$$1 \le d_i$$$ and $$$\sum_{i=1 \sim M}\limits d_i = K$$$.
There are two key values under the constraints $$$1 \le d_i$$$ and $$$\sum_{i=1 \sim M}\limits d_i = K$$$, one is the minimum value of $$$\max_{1 \le i \le M}\limits{(\left\lceil \frac{a_i}{d_i} \right \rceil)}$$$ (Let's call it $$$U$$$ after), another is the maximum value of $$$\min_{1 \le i \le M}\limits{(\left\lfloor \frac{a_i}{d_i} \right \rfloor)}$$$ (Let's call it $$$D$$$ after). $$$L$$$ and $$$U$$$ can be calculated by binary searching with time complexity $$$O(M log M)$$$. (This part is relatively easy so I won't mention it here.)
There are two conditions after calculating $$$L$$$ and $$$U$$$. One is, for all valid $$$i$$$, there exists at least one positive integer $$$d_i$$$ such that $$$L \le \left\lfloor \frac{a_i}{d_i} \right \rfloor \le \left\lceil \frac{a_i}{d_i} \right \rceil \le U$$$. In this case, the answer is just $$$U - L$$$. proof is as below.
Let $$$du_i$$$ as the largest positive integer such that $$$L \le \left\lfloor \frac{a_i}{d_i} \right \rfloor$$$ and $$$dl_i$$$ as the smallest positive integer such that $$$\left\lceil \frac{a_i}{d_i} \right \rceil \le U$$$. By the define of $$$L$$$ and $$$U$$$, we can get $$$\sum\limits_{i=1 \sim M} du_i \ge K$$$ and $$$\sum\limits_{i=1 \sim M} dl_i \le K$$$. So we always can choose some d_i where $$$d_l \le d_i \le d_u$$$ such that $$$\sum\limits_{i=1 \sim M} d_i = K$$$ and $$$L \le \left\lfloor \frac{a_i}{d_i} \right \rfloor \le \left\lceil \frac{a_i}{d_i} \right \rceil \le U$$$.
Now the essential condition is resolved. Another condition is there are some indices $$$i$$$ that we cannot find any positive integer $$$d_i$$$ such that $$$L \le \left\lfloor \frac{a_i}{d_i} \right \rfloor \le \left\lceil \frac{a_i}{d_i} \right \rceil \le U$$$. Let's call the set of these indices as $$$I$$$. For each element $$$j \in I$$$, let's calculate another two key values for index $$$j$$$. That is, we want to know the closest two values of $$$\frac{a_j}{d_j}$$$ near to range $$$[L, U]$$$ (one is above $$$[L,U]$$$ another is below $$$[L,U]$$$). Formulaically say, let $$$v$$$ be the smallest $$$d_j$$$ such that $$$\left\lfloor \frac{a_j}{d_j} \right \rfloor < L$$$ and call $$$\left\lfloor \frac{a_j}{v} \right \rfloor$$$ as $$$x_j$$$. And let $$$u$$$ be the largest $$$d_j$$$ such that $$$\left\lceil \frac{a_j}{d_j} \right \rceil > U$$$ and call $$$\left\lceil \frac{a_j}{u} \right \rceil$$$ as $$$y_j$$$. Imaging we have a set $$$S$$$ initially contains two positive integer $$$L$$$ and $$$U$$$. Now for each $$$j \in I$$$, we want to choose either $$$x_i$$$ or $$$y_i$$$ to add to $$$S$$$. Then the minimum possbile value of difference between largest element and smallest element in $$$S$$$ is the answer in this condition. The minimum possible value can be calculated as below.
Initially, for all $$$j \in I$$$, we choose $$$y_j$$$ to add to the set $$$S$$$. Then iterate from largest $$$y_j$$$ to smallest $$$y_j$$$. In each iteration, we remove $$$y_j$$$ from $$$S$$$ and add $$$x_j$$$ to $$$S$$$. The minimum possible value will exist during the process. These steps can also be done in time complexity $$$O(M log M)$$$.
The proof of correctness of the second condition is almost same as the first condition. We always can adjust $$$d_i$$$ such that $$$\sum\limits_{i=1 \sim M} d_i$$$ equal to $$$K$$$ for constructed result.
The overall time complexity is $$$O(m log m)$$$ for the above method.
In the end, I want to thanks everyone who takes part in this contest. The worth of the contest will reveal on you, when you learn thing from these problems. Thanks a lot.