题目描述

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数 n。

接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0<n≤105,
0≤ai<2147483648

输入样例：

4
1
1
2
2

输出样例：

1
2

样例

blablabla

前面已经有人给出了很好的解释, 我在这里主要解释一下为什么在操作次数最少的情况下，最终序列的有 abs(pos - nag) + 1 种结果

当我们使用差分数组的时候，若要使原数组的每一项相等，则需使差分数组从第二项开始全都为零，pos = |sum(正数)|, nag = |sum(负数|,要想使得操作次数尽可能地少，则需使得正数--, 负数++

当我们操作了 min (pos, nag)次后，数组中还有需要有abs(pos - nag)次操作，这里要么选择和第一项，要么就是 n+1 项，而且操作只有一种选择，因为剩下的全是正数或者是负数，然而只有改变差分数组的第一项才能改变原数组，因为差分数组最后的结果一定是 b1 = 某个数, b2......bn = 0,所以只有操作到第一项才能改变最终结果，从上面可知我们还需要操作abs(pos - nag)次，操作到第一项的次数可能为 0， 1，2.......abs(pos - nag)次，每一种操作次数都是一种结果，所以一共有abs(pos - nag) + 1种结果