Description：

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

$1\le n \le 100000$

Solution：

不难想到差分后转化为使得 $2\sim n$ 都为 $0$ ，每一次操作可以任选两个一个加一一个减一，或者选一个加一或减一，为了让操作数最少应该尽量选操作两个的，于是统计一下差分数组正权之和 $ans1$ 和负权之和 $ans2$ ，第一问的答案就是 $\min(ans1,ans2)+|ans1-ans2|=\max(ans1,ans2)$ ，第二问的话，首先 $min(ans1,ans2)$ 的操作是不会变的， $|ans1-ans2|$ 这些操作可以操作在 $1$ 上也可以操作在 $n+1$ 上，每一种都对应一个最终结果，所以第二问的答案就是 $|ans1-ans2|+1$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 100010

ll a[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)a[i] = read();

	ll ans1 = 0,ans2 = 0;

	for(int i = 2;i <= n;++i)

	{

		if(a[i] >= a[i - 1])ans1 += a[i] - a[i - 1];

		else ans2 += a[i - 1] - a[i];

	}

	cout << max(ans1,ans2) << endl << llabs(ans1 - ans2) + 1 << endl;

	return 0;

}