题目描述

你负责在托伦郊区开发新的地产项目。你已经决定沿一条主街建设 $n$ 块地产，编号从 $1$ 到 $n$。这片区域地势有些起伏，第 $i$ 块地产的海拔高度为 $a_i$ 厘米。

然而，市场调查显示，没人愿意购买位于坡地上的地产。形式化地，对于海拔高度 $a_1, a_2, \ldots, a_n$，坡地是指一个连续子序列 $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, i+1, \ldots, j, j+1$ 的一段连续地产，其中位置 $i, i+1, \ldots, j$ 的所有地产海拔高度均为某个值 $h$，且 $h$ 严格介于 $a_{i-1}$ 和 $a_{j+1}$ 之间。

你可以将任意一块地产的海拔高度增加或减少任意整数值，但你希望尽可能减少总的工作量。你的任务是确定消除所有坡地所需的最小海拔总变化量。也就是说，你需要找到一组没有坡地的新海拔高度 $b_1, b_2, \ldots, b_n$，使得 $|a_1 - b_1| + |a_2 - b_2| + \ldots + |a_n - b_n|$ 尽可能小。新海拔高度 $b_i$ 必须为整数（注意，这里不要求为正数），且对 $b_i$ 没有其他限制。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^{5})$，表示主街上的地产数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^{9})$，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 块地产的初始海拔高度。

输出格式

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

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

5

数据范围与提示

详细子任务附加限制及分值如下表所示。