P11569 "chaynOI R1 T2" Drawing Software

### 14:27 Added the sample explanation for T2. 

You are given a sequence $a$. You can perform at most $k$ "pen down" operations. Each time, choose a position $p(1 \le p \le n)$ and set $a_p \gets a_p + 1$ (that is, add $1$ to the $p$-th term of $a$). Find the number of possible final sequences such that $a$ becomes an arithmetic progression with a non-negative common difference.

The first line contains two integers $n, k$. The second line contains $n$ integers, representing the sequence $a$.

Output one integer in one line, representing the answer.

### Sample Explanation There are $(1,2,3,4,5)$ and $(2,3,4,5,6)$, $2$ possibilities in total. ### Constraints For $100\%$ of the testdata, $1 \le n, a_i \le 10^6$, and $k \le 10^7$. **This problem uses bundled tests.** + Subtask 1 (20 pts): $n, k \le 100$. + Subtask 2 (15 pts): $n \le 100$. + Subtask 3 (15 pts): $k \le 10^5$. + Subtask 4 (50 pts): No special constraints. Translated by ChatGPT 5