[BZOJ3043]IncDec Sequence

Description
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

Input
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。

Output
第一行输出最少操作次数
第二行输出最终能得到多少种结果

Sample Input
4
1
1
2
2

Sample Output

1
2

HINT
对于100%的数据，n=100000，0<=ai<2147483648

---

我们考虑把读入顺序作为第一关键字，权值作为第二关键字，在二维平面上描出一些折线

如果我们要让所有的数变为v，则画一条y=v的线，并将坐标轴平移，使得x轴与那条直线重合，这样我们改值相当于将所有的折线上下平移

那么对于某条折线图，答案为所有的峰值减去谷值。我们可以发现，[1,n]中峰值减去谷值是不变的，那么答案的改变就在于v[1]、v[n]与0的关系

我们考虑，如果v[1]、v[n]相同，那么我们让数轴挪动到v[1]高度，即可让答案最优

如果v[1]、v[n]不同，那么数轴在两个数之间挪动，答案不会改变；但让两个数都位于数轴的同侧后，答案一定会增加

因此我们直接令v=v[1]，求出第一问的答案，第二问答案即为|v[1]-v[n]|

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
    int x=0,f=1; char ch=gc();
    for (;ch<'0'||ch>'9';ch=gc())   if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}
inline int read(){
    int x=0,f=1; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)    putchar('-'),x=-x;
    if (x>9)    print(x/10);
    putchar(x%10+'0');
}
const int N=1e5;
ll v[N+10],n,Ans,Last;
int main(){
    scanf("%lld",&n);
    ll Ans=0,Last=0;
    for (int i=1;i<=n;i++)  scanf("%lld",v+i);
    for (int i=1;i<=n;i++){
        ll tmp=v[i]-v[1];
        if ((tmp<0)^(Last<0))   Last=0;
        if (tmp>0)  Ans+=max(0ll,tmp-Last);
        if (tmp<0)  Ans+=max(0ll,Last-tmp);
        Last=tmp;
    }
    printf("%lld\n",Ans);
    printf("%lld\n",abs(v[1]-v[n])+1);
    return 0;
}