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

• 至少需要多少次操作才能使数列中的所有数都一样。

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

输入

第一行为$n$。$1 \leq n \leq 100000$

接下来$n$行$n$个数。每个数不超过$int$类型。

输出

两个数，第一个数为至少需要多少次操作才能使数列中的所有数都一样。

第二个数为在保证最少次数的前提下，最终得到的数列有多少种。

样例

样例输入1

4
1
1
2
2

样例输出1

1
2