Non‐Decreasing Sequence Transformation

You are given a sequence of n positive integers \(A[1], A[2], \dots, A[n]\). Your task is to transform this sequence into a non‐decreasing sequence \(B[1], B[2], \dots, B[n]\) (i.e. \(B[i] \le B[i+1]\) for all \(1 \le i < n\)) by changing each element. For each position \(j\), the cost of changing \(A[j]\) to \(B[j]\) is \(|A[j] - B[j]|\). Define the overall modification cost as

\(Ans = \max_{1 \le j \le n} |A[j]-B[j]|\).

You need to find the minimum possible \(Ans\) such that there exists a sequence \(B\) which is non-decreasing and each \(B[j]\) is a positive integer and \(|A[j]-B[j]| \le Ans\) for every \(j\).

Note: If there are multiple valid sequences \(B\) achieving the minimum \(Ans\), you only need to output the value of \(Ans\).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), which is the length of the sequence.

The second line contains n positive integers \(A[1], A[2], \dots, A[n]\) separated by spaces. Each \(A[i]\) is at most 10⁹.

outputFormat

Output a single integer, representing the minimum possible \(Ans\) such that there exists a non-decreasing sequence \(B[1], B[2], \dots, B[n]\) with \(|A[j]-B[j]| \le Ans\) for all \(1 \le j \le n\).

sample

5
1 3 2 4 5

1