Untitled

bool isValid(vector<int>& arr, int n, int k, int maxDiff) {
    int changes = 0;
    vector<int> modified = arr;

    for (int i = 0; i < n - 1; ++i) {
        if (abs(modified[i + 1] - modified[i]) > maxDiff) {
            modified[i + 1] = modified[i] + (modified[i + 1] > modified[i] ? maxDiff : -maxDiff);
            changes++;
        }
        if (changes > k) return false;
    }
    return true;
}
int minimizeHardness(vector<int>& arr, int n, int k) {
    if (n <= 1) return 0;

    int left = 0, right = *max_element(arr.begin(), arr.end()) - *min_element(arr.begin(), arr.end());
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (isValid(arr, n, k, mid)) {
            result = mid; 
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}