Minimum Square Cost :
Difficulty Level : Easy
Submissions : 140
Asked In :
Marks :10
: 2 | : 0
The cost of Array $$$A$$$ is defined as:
$$$\Sigma_{1}^{n-1} = (A[i] - A[i-1])^2 $$$, 0 based indexing.
Insert any integer in any place in the array. Find the minimum possible cost after 1 such insertion.
Input
The first line contains $$$1 \le N \le 10^4$$$, denoting the number of elements in array $$$A$$$
Second line contains $$$N$$$ integers denoting elements of array $$$A$$$ ,$$$1 \le A[i] \le 10^5$$$
Output
One Integers denoting minimum cost after 1 insertion
Examples
Input
5 1 3 5 2 10
Output
49
Input
4 4 7 1 4
Output
36
