圆环上有 $n$ 个位置，依次编号为 $1$ 到 $n$。位置 $i$ 和 $i+1$ 相邻，位置 $n$ 和 $1$ 也相邻。

考虑 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$。我们将它们以某种方式排列在圆环上，使得每个位置恰好放置一个整数。一种排列的代价定义为所有相邻整数之差的绝对值之和。

当且仅当至少有一个整数在两种排列中的位置不同时，我们认为这两种排列是不同的。

你需要求出排列的最大代价。此外，计算达到该代价的不同排列的数量。由于数量可能非常大，请将其对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

保证 $a_1, a_2, \dots, a_n$ 两两不同。

输出格式

输出一行，包含两个整数。第一个整数为最大代价，第二个整数为达到该代价的不同排列数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

3
1 2 3

样例输出 1

4 6

样例输入 2

4
2 4 8 16

样例输出 2

36 8