思考下什么样的 \(l,r\) 是合法的：显然对于一组长度为 \(len\) 的空隙，要使得相邻两个 A 之间的距离在 \([l,r]\) 中，你新插入的 A 的个数应该位于 \([\lceil\dfrac{len}{r}\rceil-1,\lfloor\dfrac{len}{l}\rfloor-1]\) 中。因此合法的充要条件当且仅当所有这样的区间均非空，并且它们相加能凑出 \(k\) 出来，即
- \(\sum\lceil\dfrac{len_i}{r}\rceil-1\le k\le\sum\lfloor\dfrac{len}{l}\rfloor-1\)
- \(\lceil\dfrac{len_i}{r}\rceil\le\lfloor\dfrac{len_i}{l}\rfloor\)
第一个条件成立当且仅当 \(L\le L_0\) 且 \(R\ge R_0\)，其中 \(L_0,R_0\) 为某个可以二分出来的定值。考虑第二个条件。如果把 \((L_0,R_0)\) 带进去之后合法那么答案就是 \(R_0-L_0\)。否则对于一个不符合这个要求的二元组，必然有 \(\lceil\dfrac{len_i}{R_0}\rceil-\lfloor\dfrac{len_i}{L_0}\rfloor=1\)，此时要让它变得合法，要么使得 \(\lfloor\dfrac{len_i}{l}\rfloor=\lfloor\dfrac{len_i}{L_0}\rfloor-1\)，要么使得 \(\lceil\dfrac{len_i}{r}\rceil=\lceil\dfrac{len_i}{R_0}\rceil+1\)，这个限制可以改写为，要么 \(l\le u\) 要么 \(r\ge v\)，其中 \(u,v\) 为定值。这样问题就解决了，按第一维排序后维护第二维的限制即可。
const int MAXN=4e5;
const ll INF=1e18;
ll n,k,a[MAXN+5],b[MAXN+5],L,R,res=INF,mx[MAXN+5];int m;
void mian(){
scanf("%lld%d%lld",&n,&m,&k);k+=m+1;res=INF;
for(int i=1;i<=m;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++)b[i]=a[i]-a[i-1];b[m+1]=n-a[m];
ll _L=1,_R=n;
while(_L<=_R){
ll mid=_L+_R>>1,sum=0;
for(int i=1;i<=m+1;i++)sum+=b[i]/mid;
if(sum>=k)L=mid,_L=mid+1;
else _R=mid-1;
}
_L=1,_R=n;
while(_L<=_R){
ll mid=_L+_R>>1,sum=0;
for(int i=1;i<=m+1;i++)sum+=(b[i]+mid-1)/mid;
if(sum<=k)R=mid,_R=mid-1;
else _L=mid+1;
}
vector<pair<ll,ll> >vec;
vec.pb(mp(-INF,R));vec.pb(mp(L,INF));
for(int i=1;i<=m+1;i++){
ll xl=b[i]/L,xr=(b[i]+R-1)/R;
if(xr>xl){
_L=1,_R=n+1;ll pl=-INF,pr=INF;
while(_L<=_R){
ll mid=_L+_R>>1;
if((b[i]+mid-1)/mid<=xl)pr=mid,_R=mid-1;
else _L=mid+1;
}
_L=1,_R=n+1;
while(_L<=_R){
ll mid=_L+_R>>1;
if(b[i]/mid>=xr)pl=mid,_L=mid+1;
else _R=mid-1;
}
vec.pb(mp(pl,pr));
}
}
sort(vec.begin(),vec.end());mx[0]=vec[0].se;
for(int i=1;i<vec.size();i++)mx[i]=max(mx[i-1],vec[i].se);
for(int i=1;i<vec.size();i++)chkmin(res,mx[i-1]-vec[i].fi);
printf("%lld\n",res);
}
int main(){
int qu;cin>>qu;while(qu--)mian();
}