您负责在托伦 (Toruń) 郊区开发一个新的房地产项目。您已决定沿一条主街建造 $n$ 块地块，这些地块从 $1$ 到 $n$ 编号。该区域地势略有起伏，第 $i$ 块地块的海拔高度为 $a_i$ 厘米。

然而，市场调研显示，没有人愿意购买建在坡地上的房产。形式化地，对于给定的海拔序列 $a_1, a_2, \ldots, a_n$，若一个由地块 $i-1, i, \ldots, j, j+1$ 对应的连续海拔子序列 $a_{i-1}, a_i, \ldots, a_j, a_{j+1}$（其中 $2 \leq i \leq j \leq n-1$）满足下列任一条件，则称其构成一片坡地：

• $a_{i-1} < a_i = a_{i+1} = \ldots = a_j < a_{j+1}$；
• $a_{i-1} > a_i = a_{i+1} = \ldots = a_j > a_{j+1}$。

直观地讲，一片坡地是指一片横跨位置 $i-1, i, \ldots, j, j+1$ 的连续地块，其中处于中间部分（位置 $i, i+1, \ldots, j$）的所有地块具有相同海拔高度 $h$，且 $h$ 严格介于两端地块（位置 $i-1$ 和 $j+1$）的海拔 $a_{i-1}$ 和 $a_{j+1}$ 之间。

您可以将任一地块的海拔高度增加或减少任意整数值，但希望使总的改动量尽可能小。您的任务是，确定消除所有坡地所需付出的最小海拔总改动量。也就是说，您需要找到一组新的海拔高度 $b_1, b_2, \ldots, b_n$，使得修改后的地块上不再存在任何坡地，并且总改动量 $\sum_{k=1}^{n} |a_k - b_k|$ 达到最小。新的海拔高度 $b_i$ 必须是整数（请注意，它们不必为正数），此外对 $b_i$ 的值没有其他限制。

Input

第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^{5})$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^{9})$。

Output

输出消除所有坡地所需的最小海拔总变化量。

Example

Input

11
7 2 1 2 5 7 8 8 10 8 8

Output

5

Explanation

见原题面图。

Scoring