Given an array arr of N integers. Each array has some hardness

hardness = max abs(arr[i+1]-arr[i]) for all 1<=i<=N-1

And hardness = 0 if N<=1

You are given a number K you can change at most K elements of the array. You have to minimize the hardness of the array

Both N and K were less than 2000

where arr[i]>=-1e9 and arr[i]<=1e9