Background

14:27 Added the sample explanation for T2.

Problem Description

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.

Input Format

The first line contains two integers $n, k$.

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

Output Format

Output one integer in one line, representing the answer.

5 6
1 2 3 4 5

2

Hint

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