Problem A2: Snake Scales (Chapter 2)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

bool valid(ll mid, vector<ll>& arr, ll n)
{
    vector<ll> vis(n, 0);
    for (ll i = 0; i < n; i++) {
        if (vis[i])
            continue;
        if (arr[i] <= mid) {
            vis[i] = 1;
            for (ll l = i - 1; l >= 0; l--) {
                if (vis[l])
                    break;
                if (abs(arr[l] - arr[l + 1]) <= mid) {
                    vis[l] = 1;
                } else {
                    break;
                }
            }
            for (ll r = i + 1; r < n; r++) {
                if (vis[r])
                    break;
                if (abs(arr[r] - arr[r - 1]) <= mid) {
                    vis[r] = 1;
                } else {
                    break;
                }
            }
        }
    }
    return accumulate(vis.begin(), vis.end(), 0ll) == n;
}

void Solve()
{
    ll n;
    cin >> n;
    vector<ll> arr(n);
    for (auto& it : arr)
        cin >> it;
    ll ans = 1e9;
    ll lo = 0, hi = 1e9;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        if (valid(mid, arr, n)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << '\n';
}

int32_t main()
{
    freopen("input.txt", "r+", stdin);
    freopen("output.txt", "w+", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)
// Coded for CPS Academy