Equalizing Array with Subarray Operations

Given an array (a_1,a_2,\dots,a_n) of length (n), you are allowed to perform the following operation: choose three integers (l, r, x) with (1 \le l \le r \le n) and (x \in \mathbb{Z}) and add (x) to each element in the subarray (a_l, a_{l+1}, \dots, a_r). Such an operation adds a constant amount over a contiguous segment. The goal is to make all elements of (a) equal, using as few operations as possible. In addition, you are asked to count the number of different operation sequences that achieve this minimum. Two operation sequences are considered different if and only if at least one step chooses a different triple ((l,r,x)). Note that doing nothing (i.e. 0 operations) is a valid sequence if the array is already equal.

A useful observation is to consider the difference array (d_i=a_{i+1}-a_i) for (i=1,2,\dots,n-1). An operation only affects at most two entries in this difference array: if you perform an operation ((l,r,x)) then it adds (x) to (d_{l-1}) (if (l>1)) and subtracts (x) from (d_r) (if (r<n)). Making (a) constant is equivalent to setting all (d_i=0). In order to cancel nonzero (d_i)’s, one may sometimes cancel two differences using one operation if they occur with opposite signs and the positive one appears before the negative one. In particular, if (k) is the number of nonzero differences and if for each absolute value (v) one can pair some occurrences of (v) and (-v) (using a pair ( (i,j)) with (i<j)) then the minimal number of operations needed is (k-M) where (M) is the total number of such pairs (each pair fixed by a single operation). The remaining, unpaired differences (a total of (k-2M) differences) can be fixed individually in 2 ways (by adding the needed value at one of the two boundaries). Hence, the answer is composed of two numbers:

• The minimum number of operations needed is (k-M).
• The number of different minimal operation sequences is (\Bigl(\prod_{v>0}{\rm ways}(v)\Bigr)\cdot2^{k-2M}) modulo (10^9+7), where for each positive integer (v) the factor ({\rm ways}(v)) is the number of ways to choose a maximum pairing between indices where (d_i=v) and indices where (d_j=-v) (with (i<j)).

Your task is to compute these two numbers given (a).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^5)).

The second line contains (n) integers (a_1, a_2, \dots, a_n) ((|a_i| \le 10^9)).

outputFormat

Output two integers: the minimum number of operations required, and the number of different sequences of operations achieving that minimum (modulo (10^9+7)).

sample

3
1 2 3

1 2