Crossing the Stepping Stones (large)

Interview

Time limit2sMemory limit1024 MB

Summary

Find the smallest energy limit K such that some path from stone 1 to stone N, jumping rightward, keeps every jump cost (j-i)*(1+|Ai-Aj|) within K.

Level: Medium7 of 10
Topics: Binary search, Greedy, Dynamic programming, Array
Solved: No attempts yet

Problem

$N$ stones are lined up in a row. The stones are given the numbers $A_{1}, A_{2}, ..., A_{i}, ..., A_{N}$ from left to right. You want to start at the leftmost stone and cross to the rightmost stone.

You can only move to the right.
When moving from the $i$ -th stone to the $j$ -th stone $(i < j)$ , you use $(j - i) \times (1 + |A_{i} - A_{j}|)$ units of energy.
For each single crossing between stones, the energy you can use is at most $K$ .

Find the minimum $K$ among all ways to cross from the leftmost stone to the rightmost stone.

Input

The first line gives the number of stones $N$ , separated by spaces.

The second line gives the $N$ stone numbers $A_{i}$ , separated by spaces.

Output

Print the minimum possible $K$ among all ways to cross from the leftmost stone to the rightmost stone.

Constraints

$2 \le N \le 5,000$
$1 \le A_{i} \le 1,000,000$
$A_{i}$ is an integer

Examples2

Example 1
Input
```
5
1 4 1 3 1
```
Expected output
```
2
```
Example 2
Input
```
5
1 5 2 1 6
```
Expected output
```
6
```