Description

You are given an array $a_1, a_2, \ldots, a_n$ of length $n$.

You may choose any three integers $l, r, x\ (1 \le l \le r \le n$, $x \in \mathbb Z)$, and add $x$ to each of $a_l, a_{l+1}, \ldots, a_r$. This is called one operation.

Find the minimum number of operations needed to make all elements in $a$ equal, and also find the number of different optimal plans that achieve this minimum number of operations.

Since the number of plans may be very large, output it modulo $10^9 + 7$.

Two plans are considered the same if and only if, for every operation, the chosen $(l, r, x)$ are exactly the same.

In particular, performing no operation is also considered a valid plan.

Input Format

The first line contains one integer $n$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

Output Format

The first line contains one integer, the minimum number of operations.

The second line contains one integer, the number of plans modulo $10^9 + 7$.

3
1 2 3

2
16

Hint

[Sample 1 Explanation]

One feasible plan is: $(l, r, x) = (1, 1, 1), (3, 3, -1)$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (1 point): $n = 2$.
• Subtask 2 (5 points): $n = 3$.
• Subtask 3 (14 points): $a$ is guaranteed to be non-increasing or non-decreasing.
• Subtask 4 (20 points): $n \le 10$.
• Subtask 5 (20 points): $n \le 16$.
• Subtask 6 (40 points): no special restrictions.

For $100\%$ of the testdata, $1 \le n \le 18$, $-10^9 \le a \le 10^9$.

Translated by ChatGPT 5