P7718 "EZEC-10" Equalization

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.

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

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

**[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