Minimize Maximum Difference

Given a sequence (a) of (n) integers and an integer (k), you are allowed to perform at most (k) operations. In each operation, you can change one element to any integer between (0) and (m) (inclusive). The objective is to minimize the maximum absolute difference between any two consecutive elements in the sequence. Formally, if the resulting sequence is (a_1, a_2, \dots, a_n), you must minimize (\max_{1 \le i < n} |a_i - a_{i+1}|). An efficient approach to solve this problem is to perform a binary search on the answer. Note that the absolute difference between two consecutive elements is given by (|a_i - a_{i+1}|).

inputFormat

The first line contains three integers (n), (k), and (m) separated by spaces. The second line contains (n) integers representing the sequence (a).

outputFormat

Output a single integer, which is the minimized maximum absolute difference between any two consecutive elements after at most (k) operations.## sample

5 2 10
1 5 9 4 8

4