Counting Non‐negative Arithmetic Progression Transformations

You are given a sequence \(a = [a_1, a_2, \dots, a_n]\) and an integer \(k\). You are allowed to perform at most \(k\) operations. In each operation, you choose an index \(p\) \((1 \le p \le n)\) and increment \(a_p\) by 1, i.e. \(a_p \gets a_p+1\). Your task is to count the number of distinct final sequences (arithmetic progressions) that can be obtained such that the final sequence forms an arithmetic progression with a non-negative common difference.

More formally, after applying some (possibly zero) operations (at most \(k\) in total), the new sequence \(b\) satisfies \[ b_i = a_i + x_i, \quad \text{with } x_i \ge 0 \text{ and } \sum_{i=1}^{n} x_i \le k, \] and there exist integers \(A\) and \(d \ge 0\) such that \[ b_i = A + (i-1)d, \quad 1 \le i \le n. \]

Notice that for each position \(i\), we must have: \[ A + (i-1)d \ge a_i, \quad \text{or equivalently } A \ge a_i - (i-1)d. \]

Let \[ L = \max_{1 \le i \le n} \{a_i - (i-1)d\}. \] Then for a fixed \(d\), the first term \(A\) can be any integer such that \(A \ge L\) and the total cost \[ \text{cost} = \Bigl(\sum_{i=1}^{n} (A + (i-1)d - a_i)\Bigr) = nA + \frac{n(n-1)}{2}d - \sum_{i=1}^{n}a_i \n\] does not exceed \(k\). For a fixed \(d\), if we denote: \[ A_{\text{min}} = L, \quad A_{\text{max}} = \left\lfloor\frac{k - \frac{n(n-1)}{2}d + \sum_{i=1}^{n}a_i}{n}\right\rfloor, \] then the number of valid choices for \(A\) is (if \(A_{\text{max}} \ge A_{\text{min}}\)) \[ \max(0, A_{\text{max}} - A_{\text{min}} + 1). \]

Your task is to compute the total number of valid final sequences over all possible \(d \ge 0\) such that the operations used do not exceed \(k\).

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le 10^5, 0 \le k \le 10^9)\) representing the length of the sequence and the maximum number of operations allowed.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^9)\) representing the initial sequence.

outputFormat

Output one integer, the total number of distinct final arithmetic progression sequences that can be formed under the given conditions.

sample

3 5
2 2 2

3