题意描述

今天是个神圣的日子，因为LHX教主要进行一段长途旅行。

但是教主毕竟是教主，他喜欢走自己的路，让别人目瞪口呆。

为什么呢，因为这条路线高低不平，而且是相当的严重。

但是教主有自己的办法，他会魔法。

这段路可以用一个长度为$N$的序列$a_i$来表示，$a_i$表示了第$i$这段路的高度。

教主即使会使用魔法他还是个人，教主如果想穿越这条路线，他必须从第$1$段路开始走，走到第$N$段，从第$i$段走到第$i+1$段路需要消耗$|a_{i + 1} - a_i|$点体力。

为了节省体力，教主使出了他神奇的魔法。

教主的魔法可以将一段路高度变高或者变低，但是使用魔法也需要体力，改变一段路$H$的高度就需要消耗$H$的体力。

接着，LHX教主想规划下如何调整路段高度后穿越，使得总体力消耗最小。

输入格式

输入的第1行为一个正整数$N$，表示了这条路线的长度。

第2行有$N$个正整数，相邻两个正整数用空格隔开，描述了$a_i$这个序列。

输出格式

输出仅包括一个非负整数，为最小的总体力消耗。

注意：答案可能超过$2^31-1$。因此，请使用int64或者long long类型保存答案。

Input & Output ‘s examples

Input ‘s eg

3
3 4 1

Output ‘s eg

数据范围与约定

对于$10\%$的数据，有$N≤10$；

对于$30\%$的数据，有$a_i≤10^3$；

对于$40\%$的数据，有$N≤10^3$；

对于$100\%$的数据，有$N≤10^5，a_i≤10^7$。

分析

~~考场上唯一A掉的签到题~~

先说解法：若中间的数高于或低于两边(即出现下图状况时)，则将中间的数变成两边的数中较近的那个。

证明如下：

设连续的三个数高度为$l , mid , r$。

若$l < mid > r$，即出现上图左侧的情况时，若我们直接走，消耗的体力为$|mid - l| + |r - mid|$(即下图蓝色部分)

这时，若我们把$mid$降至与$min(l , r)$（此时为$r$）一样高时，则我们消耗的体力为$|r - l| + |mid - r|$，省去了一段$mid - r$。

因此，这样做是更优的。

降至较近的那个是因为，若降到较远的那个，下降时消耗的体力值与走过的距离均会更大。

至于图示中右图的情况，请各位读者结合上面的讲解自行证明。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

ll n , a[N];
ll ans = 0;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 2; i <= n - 1; i ++){
        if(a[i - 1] < a[i] && a[i] > a[i + 1]){     //若中间比两边高
            ll maxn = max(a[i - 1] , a[i + 1]);
            ans += abs(maxn - a[i]);
            a[i] = maxn;
        }
        if(a[i] < a[i - 1] && a[i + 1] > a[i]){     //若中间比两边低
            ll minn = min(a[i - 1] , a[i + 1]);
            ans += abs(minn - a[i]);
            a[i] = minn;
        }
    }

    for(int i = 2; i <= n; i ++){       //统计答案
        ans += abs(a[i] - a[i - 1]);
    }
    cout << ans << "\n";
    return 0;
}