171-div2-B

#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define ar array
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

bool is_possible(int n, const vector<ll> &a, ll k){
    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){
        vector<bool> next0(n + 1, false);
        vector<bool> next1(n + 1, false);

        if (dp0[i]){
            if (i + 1 < n && abs(a[i + 1] - a[i]) <= k){
                next0[i + 2] = true;
            }
            if (k >= 1){
                next1[i + 1] = true;
            }
        }

        if (dp1[i]){
            if (i + 1 < n && abs(a[i + 1] - a[i]) <= k){
                next1[i + 2] = true;
            }
        }

        for (int j = 0; j <= n; ++j){
            if (next0[j])
                dp0[j] = true;
            if (next1[j])
                dp1[j] = true;
        }
    }

    return dp0[n] || dp1[n];
}

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    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 << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++){
        solve();
    }
    return 0;
}