I. Snow Clearing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A blizzard has just hit the North Pole and the main road has been covered with lots of snow! Formally, the road has $$$n$$$ segments, numbered $$$1\ldots n$$$, and the $$$i$$$th segment has a height of $$$h_i$$$ in inches. We can assume that there are road segments at positions $$$0$$$ and $$$n+1$$$ and that they both of height $$$0$$$. Santa needs the road cleared asap but he can only clear the snow by using his magic snow plow. To use the plow, he can place it on some segment along the road, and reduce the height of an higher adjacent cell until it is equal to the lower one. The time it takes to do this is equal to the square of the absolute difference between the cell that the plow is on and the cell whose height is being reduced.

Formally, for one operation choose $$$i$$$ and $$$j$$$ such that $$$0 \leq i, j \leq n + 1$$$, $$$|i - j| = 1$$$, and $$$h_i \lt h_j$$$. The operation takes $$$(h_j - h_i)^2$$$ minutes. Then, change the value of $$$h_j$$$ to $$$h_i$$$.

The total time taken to clear the road is equal to the sum of the time taken during each operation. Help Santa by finding the minimum time needed to clear the road.

Input

The first line of input will contain a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)— representing the number of road segments.

The next line will contain $$$n$$$ integers $$$h_1, ..., h_n$$$ ($$$1 \leq h_i \leq 10^6$$$) — $$$h_i$$$ denoting the height in inches of the $$$i$$$th road segment.

Output

Output a single integer on its own line denoting the minimum time needed to clear all of the snow.

Examples
Input
5
1 2 4 3 1
Output
11
Input
4
1 4 3 3
Output
17
Input
5
1000000 1 1000000 1000000 1
Output
2999994000008