503008 - 增减序列

【题目描述】增减序列(incdec)

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

Input

第一行输入正整数 n(0<n≤105)。 接下来n行,每行输入一个整数,第i+1行的整数代表 ai(0≤ai<2147483648)。

Output

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

Examples

Input

4
1
1
2
2

Output

1
2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题