7CxwDe - Online Java Compiler & Debugging Tool

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tok;

    public static void main(String[] args) throws IOException {
        int T = nextInt();
        while (T-- > 0) {
            int n = nextInt();
            long k = nextLong();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }

            long left = 0, right = 0;
            for (int i = 1; i < n; i++) {
                right = Math.max(right, Math.abs(a[i] - a[i-1]));
            }

            long ans = right;
            while (left <= right) {
                long mid = (left + right) / 2;
                if (check(a, mid, k)) {
                    ans = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            System.out.println(ans);
        }
    }

    private static boolean check(long[] a, long d, long k) {
        int n = a.length;
        long[] b = a.clone();
        long operations = 0;
        for (int i = 1; i < n; i++) {
            if (b[i] - b[i-1] > d) {
                operations += b[i] - b[i-1] - d;
                b[i] = b[i-1] + d;
            }
        }
        for (int i = n-2; i >= 0; i--) {
            if (b[i] - b[i+1] > d) {
                operations += b[i] - b[i+1] - d;
                b[i] = b[i+1] + d;
            }
        }
        return operations <= k;
    }

    static int nextInt() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(br.readLine());
        }
        return Integer.parseInt(tok.nextToken());
    }

    static long nextLong() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(br.readLine());
        }
        return Long.parseLong(tok.nextToken());
    }
}