33451번 - Count the Orders 다국어

문제

There are $n$ positions on a circle, numbered successively by integers from 1ドル$ to $n$. The positions $i$ and $i + 1$ are adjacent; the positions $n$ and 1ドル$ are also adjacent.

Consider $n$ distinct integers $a_1, a_2, \ldots, a_n$. We arrange them somehow on the circle, so that there is a single integer in each of the $n$ positions. The cost of an arrangement is defined as the sum of the absolute values of the difference between every two adjacent integers.

Two arrangements are different if and only if at least one integer has different positions in them.

You need to find the maximum cost of an arrangement. Additionally, calculate the number of different arrangements that have this cost. As their number can be very large, find it modulo 10ドル^9 + 7$.

입력

The first line contains a single integer $n$ (3ドル \le n \le 10^6$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ (0ドル \le a_i \le 10^9$).

It is guaranteed that $a_1, a_2, \ldots, a_n$ are pairwise distinct.

출력

Output a single line with two integers. The first one should be the maximum cost. The second one should be the number of different arrangements that have this cost, modulo 10ドル^9 + 7$.

제한

힌트