Problem Description

When Xiao Lan is bored, he randomly generates an integer array of length $n$. The $i$-th number in the array is $a_i$. He feels the randomly generated array is not very good-looking and wants to turn it into a palindrome array, that is, for any $i \in [1,n]$, it satisfies $a_i = a_{n-i+1}$.

In one operation, Xiao Lan may choose two adjacent numbers and increase both by $1$ or decrease both by $1$. He may also choose only one number and increase it by $1$ or decrease it by $1$. Find the minimum number of operations needed to make this array a palindrome array.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, separated by one space between adjacent integers.

Output Format

Output one line containing one integer, representing the answer.

4
1 2 3 4

3

Hint

[Sample Explanation]

In the first operation, increase $a_1, a_2$ by $1$, becoming $2, 3, 3, 4$.

In the next two operations, increase $a_1$ by $1$, becoming $4, 3, 3, 4$.

[Test Case Size and Conventions]

For $20\%$ of the test cases, $1 \le n \le 10$.

For all test cases, $1 \le n \le 10^5$, $-10^6 \le a_i \le 10^6$.

Translated by ChatGPT 5