Given an integer array arr, you may perform the following operation at most once:

• Choose any subset of non-adjacent indices.
• Choose a non-negative integer x.
• Add the same x to every selected element.

The resulting array must be non-decreasing, meaning arr[i] ≤ arr[i + 1] for every valid index i.

Return the minimum possible value of x; return 0 if the array is already non-decreasing and -1 if no valid operation can satisfy the requirement. Indices are zero-indexed.

Constraints:

• 1 ≤ arr.length ≤ 10⁵
• -10⁹ ≤ arr[i] ≤ 10⁹

Example 1:

Input: arr = [1, 1, 3, 2] Output: 1 Explanation: Select index 3 and add 1, producing [1, 1, 3, 3]. The array is then non-decreasing, while an increment of 0 leaves 3 greater than 2.

Example 2:

Input: arr = [1, 2, 3, 3] Output: 0

Example 3:

Input: arr = [3, 0, 3, 0, 3] Output: 3