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$.