题目描述

给定一个长度为 n 的数列 a[i]，每次可以选择一个区间 [l,r]，使这个区间内的数都加一或者都减一。

求：（1）至少需要多少次操作才能使数列中的所有数都一样。

　　（2）在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个数 n。

第二行 n 个数，为 a[1]~a[n]。

输出格式

两行，两个正整数，第一行为最少操作次数，第二行为最终得到的数列种数。

4
3 2 2 2

1
2

</p>

提示

数据范围：1 <= n <= 10^5，1 <= a[i] <= 10^9。

提示：对相邻两项作差得到差分序列 d[i]=a[i]-a[i-1]，最少操作次数为 max(正差之和, 负差之和的绝对值)，最终数列种数为 |正差之和 - 负差之和的绝对值| + 1。

本题为 OI 赛制，满分 100 分，共 10 个测试点，每个测试点 10 分。

来源

差分数组专题（2017 信息学培训）