Platforms - 3#806

Platforms - 3

1 second

128 megabytes

Easy

In older games one can run into the next situation. The hero jumps along the platforms that hang in the air. He must move himself from one side of the screen to the other. When the hero jumps from one platform to the neighboring, he spends $∣ y_{2} - y_{1} ∣^{2}$ |y_2 - y_1|^2 energy, where $y_{1}$ y_1 and $y_{2}$ y_2 are the heights where these platforms hang. The hero can make a super jump that allows him to skip one platform, but it takes him $3 \cdot ∣ y_{3} - y_{1} ∣^{2}$ 3 \cdot |y_3 - y_1|^2 energy.

You are given the heights of the platforms in order from the left side to the right. Find the minimum amount of energy to get from the $1$ -st (start) platform to the $n$ -th (last).

Input

The first line contains the number of platforms $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5). The second line contains $n$ integers — the heights of the platforms. Their values do not exceed $4000$ in absolute value.

Output

Print one integer — the minimum amount of energy.

Examples

Example

3
2 4 1

Example 1