C. Bumpy Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a small town, hidden from prying eyes in the mountains, archaeologists stumbled upon a mysterious cave. Inside, they discovered ancient manuscripts written in an unknown language. After long studies and deciphering the text, the scholars concluded that the records belong to a well-known civilization that existed thousands of years ago and contain information about a certain mathematical problem. They believe that solving this problem may be important for their research, and therefore ask you to write a program to solve it.

The problem is formulated as follows: an array $$$b$$$ is called bumpy if each of its internal elements (that is, not the first or the last) is strictly greater than or strictly less than both of its neighbors.

Initially, a certain array $$$a$$$ consisting of integers is given. In one operation, you can choose a certain element of the array and increase or decrease it by 1.

You need to determine the minimum number of operations required to make the array $$$a$$$ bumpy.

Input

The first line of input contains one integer $$$n\, (3 \le n \le 10^5)$$$ — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (-10^9\le a_i \le 10^9)$$$ — the values of the elements of the array $$$a$$$.

Output

Output the minimum number of operations required to make the array $$$a$$$ bumpy.

Examples
Input
5
1 3 5 6 5
Output
3
Input
8
-8 4 -6 5 9 -7 8 1
Output
25