#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool is_possible(int n, const vector<ll>& a, ll k) {
// dp[used][i] where used is 0 or 1, and i is the index
// Initialize two vectors for used=0 and used=1
// dp0[i] means used=0 at position i
// dp1[i] means used=1 at position i
vector<bool> dp0(n + 1, false);
vector<bool> dp1(n + 1, false);
dp0[0] = true;
dp1[0] = false;
for(int i = 0; i < n; ++i){
// Temporary next step
// Iterate through current dp0 and dp1
// Handle dp0
if(dp0[i]){
// Option 1: pair a[i] with a[i+1] if possible
if(i+1 <n && a[i+1] - a[i] <=k){
dp0[i+2] = true;
}
// Option 2: pair a[i] with an extra cell, if not used yet
if(k >=1){
dp1[i+1] = true;
}
}
// Handle dp1
if(dp1[i]){
// Option 1: pair a[i] with a[i+1] if possible
if(i+1 <n && a[i+1] - a[i] <=k){
dp1[i+2] = true;
}
// No option to pair with extra cell since already used
}
// Update dp0 and dp1
}
return dp0[n] || dp1[n];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<ll> a(n);
for(auto &x: a) cin >> x;
// Binary search for minimal k
ll left = 0, right = (ll)1e18;
ll answer = right;
while(left <= right){
ll mid = left + (right - left)/2;
if(is_possible(n, a, mid)){
answer = mid;
right = mid -1;
}
else{
left = mid +1;
}
}
cout << left << "\n";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmJvb2wgaXNfcG9zc2libGUoaW50IG4sIGNvbnN0IHZlY3RvcjxsbD4mIGEsIGxsIGspIHsKICAgIC8vIGRwW3VzZWRdW2ldIHdoZXJlIHVzZWQgaXMgMCBvciAxLCBhbmQgaSBpcyB0aGUgaW5kZXgKICAgIC8vIEluaXRpYWxpemUgdHdvIHZlY3RvcnMgZm9yIHVzZWQ9MCBhbmQgdXNlZD0xCiAgICAvLyBkcDBbaV0gbWVhbnMgdXNlZD0wIGF0IHBvc2l0aW9uIGkKICAgIC8vIGRwMVtpXSBtZWFucyB1c2VkPTEgYXQgcG9zaXRpb24gaQogICAgdmVjdG9yPGJvb2w+IGRwMChuICsgMSwgZmFsc2UpOwogICAgdmVjdG9yPGJvb2w+IGRwMShuICsgMSwgZmFsc2UpOwogICAgZHAwWzBdID0gdHJ1ZTsKICAgIGRwMVswXSA9IGZhbHNlOwogICAgCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKXsKICAgICAgICAvLyBUZW1wb3JhcnkgbmV4dCBzdGVwCiAgICAgICAgLy8gSXRlcmF0ZSB0aHJvdWdoIGN1cnJlbnQgZHAwIGFuZCBkcDEKICAgICAgICAvLyBIYW5kbGUgZHAwCiAgICAgICAgaWYoZHAwW2ldKXsKICAgICAgICAgICAgLy8gT3B0aW9uIDE6IHBhaXIgYVtpXSB3aXRoIGFbaSsxXSBpZiBwb3NzaWJsZQogICAgICAgICAgICBpZihpKzEgPG4gJiYgYVtpKzFdIC0gYVtpXSA8PWspewogICAgICAgICAgICAgICAgZHAwW2krMl0gPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIC8vIE9wdGlvbiAyOiBwYWlyIGFbaV0gd2l0aCBhbiBleHRyYSBjZWxsLCBpZiBub3QgdXNlZCB5ZXQKICAgICAgICAgICAgaWYoayA+PTEpewogICAgICAgICAgICAgICAgZHAxW2krMV0gPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIC8vIEhhbmRsZSBkcDEKICAgICAgICBpZihkcDFbaV0pewogICAgICAgICAgICAvLyBPcHRpb24gMTogcGFpciBhW2ldIHdpdGggYVtpKzFdIGlmIHBvc3NpYmxlCiAgICAgICAgICAgIGlmKGkrMSA8biAmJiBhW2krMV0gLSBhW2ldIDw9ayl7CiAgICAgICAgICAgICAgICBkcDFbaSsyXSA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgLy8gTm8gb3B0aW9uIHRvIHBhaXIgd2l0aCBleHRyYSBjZWxsIHNpbmNlIGFscmVhZHkgdXNlZAogICAgICAgIH0KICAgICAgICAvLyBVcGRhdGUgZHAwIGFuZCBkcDEKICAgIH0KICAgIHJldHVybiBkcDBbbl0gfHwgZHAxW25dOwp9CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZSgwKTsKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSh0LS0pewogICAgICAgIGludCBuOwogICAgICAgIGNpbiA+PiBuOwogICAgICAgIHZlY3RvcjxsbD4gYShuKTsKICAgICAgICBmb3IoYXV0byAmeDogYSkgY2luID4+IHg7CiAgICAgICAgLy8gQmluYXJ5IHNlYXJjaCBmb3IgbWluaW1hbCBrCiAgICAgICAgbGwgbGVmdCA9IDAsIHJpZ2h0ID0gKGxsKTFlMTg7CiAgICAgICAgbGwgYW5zd2VyID0gcmlnaHQ7CiAgICAgICAgd2hpbGUobGVmdCA8PSByaWdodCl7CiAgICAgICAgICAgIGxsIG1pZCA9IGxlZnQgKyAocmlnaHQgLSBsZWZ0KS8yOwogICAgICAgICAgICBpZihpc19wb3NzaWJsZShuLCBhLCBtaWQpKXsKICAgICAgICAgICAgICAgIGFuc3dlciA9IG1pZDsKICAgICAgICAgICAgICAgIHJpZ2h0ID0gbWlkIC0xOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBsZWZ0ID0gbWlkICsxOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgbGVmdCA8PCAiXG4iOwogICAgfQp9Cg==