E. Robot Racing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yam is racing robots! Unfortunately, his robots are out of control, so he has to stop them before they crash.

Yam has $$$N$$$ robots, each with speed $$$a_i$$$ ($$$a_i$$$ is non-decreasing). They are all positioned at the start (i.e., position $$$0$$$) of a track of length $$$L$$$ meters. For each subarray, Yam does the following:

First, he divides the robots in the subarray into $$$k$$$ groups of robots, where each robot must belong to exactly one group, and each group has at least one robot. Every second, every robot will advance $$$a_i$$$ meters forward. Then, after every second, Yam chooses a group and shoots every robot in the group, stopping them from moving forward in the future. If any robot crosses the end of the track (i.e., its position is strictly greater than $$$L$$$), then it spontaneously combusts. Define the score of this subarray as the maximum number of groups that Yam can form while ensuring that no robot spontaneously combusts. (Yam can choose to group the robots strategically to maximize the score.)

Yam thinks this is too easy, so he challenges you to find the sum of scores over all subarrays.

Input

The first line of input contains two integers $$$N$$$ and $$$L$$$ ($$$1\le N\le 2\cdot 10^5$$$, $$$1\le L\le 10^9$$$).

The following line contains $$$N$$$ integers $$$a_1, \dots, a_n$$$, ($$$1\le a_i\le L$$$).

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-3$$$ satisfy $$$N\le 200$$$.

Tests $$$4-6$$$ satisfy $$$N\le 5000$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

Output the sum of scores over all subarrays.

Example
Input
4 10
1 3 6 10
Output
17
Note

The subarray $$$[1]$$$ has score $$$1$$$ $$$-$$$ Yam creates 1 group $$$[1]$$$

The subarray $$$[3]$$$ has score $$$1$$$ $$$-$$$ Yam creates 1 group $$$[3]$$$.

The subarray $$$[6]$$$ has score $$$1$$$ $$$-$$$ Yam creates 1 group $$$[6]$$$.

The subarray $$$[10]$$$ has score $$$1$$$ $$$-$$$ Yam creates 1 group $$$[10]$$$.

The subarray $$$[1,3]$$$ has score $$$2$$$ $$$-$$$ Yam creates 2 groups, $$$[3]$$$, $$$[1]$$$ and shoots them in this order.

The subarray $$$[3,6]$$$ has score $$$2$$$ $$$-$$$ Yam creates 2 groups, $$$[6]$$$, $$$[3]$$$.

The subarray $$$[6,10]$$$ has score $$$1$$$ $$$-$$$ Yam creates 1 group, $$$[6, 10]$$$.

The subarray $$$[1,3,6]$$$ has score $$$3$$$ $$$-$$$ Yam creates 3 groups, $$$[6]$$$, $$$[3]$$$, $$$[1]$$$.

The subarray $$$[3,6,10]$$$ has score $$$2$$$ $$$-$$$ Yam creates 2 groups, $$$[6, 10]$$$, $$$[3]$$$.

The subarray $$$[1,3,6,10]$$$ has score $$$3$$$ $$$-$$$ Yam creates 3 groups, $$$[6, 10]$$$, $$$[3]$$$, $$$[1]$$$.

Thus, the sum of scores is $$$1 + 1 + 1 + 1 + 2 + 2 + 1 + 3 + 2 + 3 = 17$$$.

—

Problem Idea: Yam

Problem Preparation: jay_jayjay

Occurrences: Novice L, Advanced E