It is time to assemble again, and the instructor of Siri's company is organizing the formation. Siri's company has a total of $n$ students, where the $i$-th student has a height of $a_i$. The instructor wants to arrange them in a line to practice marching. The instructor feels that if the heights of the students in an interval are not consistent, it will not look very neat. He defines the "untidiness" of a sequence as the sum of the ranges of heights of all intervals, where the range is defined as the difference between the maximum and minimum values in the interval. The instructor wants to arrange these $n$ distinct students in a line such that the untidiness of the entire queue is minimized, and he also wants to know how many different arrangements satisfy this. However, the massive amount of calculation makes it impossible for the instructor to complete this task quickly, so he decides to ask Siri, who has the highest programming skill in the company, for help.

Formally: Given a sequence $a_1, a_2, \dots, a_n$ of length $n$, find the number of permutations $p$ such that $\sum_{l=1}^{n} \sum_{r=l}^{n} (\max(a_{p_l}, a_{p_{l+1}}, \dots, a_{p_r}) - \min(a_{p_l}, a_{p_{l+1}}, \dots, a_{p_r}))$ is minimized. Output the minimum value and the number of such arrangements modulo $998\,244\,353$.

Input

The first line contains an integer $n$ ($1 \le n \le 10^3$), representing the number of students. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), representing the heights of the $n$ students.

Output

A single line containing two integers: the minimum untidiness of the queue and the number of arrangements that achieve this minimum untidiness, modulo $998\,244\,353$. Note that the minimum untidiness itself should not be taken modulo.

Examples

Input 1

2
1 2

Output 1

1 2

Input 2

9
9 9 8 2 4 4 3 5 3

Output 2

114 16