区间加减统一数列问题

题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，每次可以选择一个区间 $[l, r]$，使下标在这个区间内的数都加一或者都减一。

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

输入格式

第一行输入正整数 $n$。

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

输出格式

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

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

输入输出样例 #1

输入 #1

4
1
1
2
2

输出 #1

1
2

输入输出样例 #2

输入 #2

5
3
1
4
1
5

输出 #2

5
1

限制条件

• $0 < n \le 10^5$
• $0 \le a_i < 2147483648$
• 所有输入均为整数

样例解释 #1

原始数列：$[1, 1, 2, 2]$

方案1：

• 将区间 $[3, 4]$ 都减1：得到 $[1, 1, 1, 1]$

方案2：

• 将区间 $[1, 2]$ 都加1：得到 $[2, 2, 2, 2]$

最少操作次数为 $1$ 次，最终可以得到 $2$ 种不同的统一数列。