406606: GYM102458 C Daniel's game

On a beautiful day in December, Daniel invites Andy to play an interesting game: Daniel will pick an array $$$A$$$ which has $$$n$$$ non-negative integers $$$A_1, A_2,..., A_n$$$ and a non-negative integer $$$M$$$. After that, Andy will randomly pick a non-empty sub-array of $$$A$$$, which means he will pick two integers $$$l, r\ (1\le l \le r \le n)$$$ và take $$$A_l, A_{l+1},..., A_r$$$ from the array $$$A$$$. Andy has to preserve the order of the taken integers.

Andy is only allowed to increase his taken integers. Suppose after doing so he receives $$$A'_l, A'_{l+1},..., A'_r$$$ where $$$A'_i \in \mathbb{Z},\ A'_i \ge A_i \forall i=\overline{l, r}$$$. However, he must follow the restriction below:

$$$$$$\sum_{i=l}^{r} A'_i - A_i\le M$$$$$$.

If $$$A'_l, A'_{l+1},..., A'_r$$$ in this order form a non-decreasing array, Daniel will award Andy with bubble tea.

Right after Andy accepts the challenge, Daniel thinks hard to lower the chance of Andy winning as much as possible. Therefore, when he thinks of array $$$A$$$, Daniel has to calculate quickly the number of non-empty sub-arrays of $$$A$$$ that Andy can pick to win this game.

After $$$\frac{21}{10}$$$ second, Daniel has to start the game by telling Andy the array. Please help him to calculate in 2 secs.

Line 1 contains 2 integers $$$n, M$$$.

Line 2 contains $$$n$$$ integers of array $$$A$$$: $$$A_1, A_2,..., A_n$$$.

Numbers on the same line are separated by spaces

An integer indicating the answer

In all testcases, $$$n \ge 1, 0\le M\le 2\times 10^{14}, 0\le A_i\le 10^{9}\ \forall i=\overline{1, n}$$$.

70 points with 3 subtasks:

1. 12 points: $$$n\le 100$$$.
2. 18 points: $$$n\le 1000$$$.
3. 40 points: $$$n\le 2\times 10^{5}$$$.

6 6
5 4 1 1 5 5

18

5 5
6 5 4 3 2

12

1 0
1234

1