A histogram is a graphical representation of a statistical distribution — a function that assigns a specific value $h_j$ to each integer $j$ between $1$ and $n$. We draw a histogram by drawing a column of width $1$ and height $h_j$ for each number $j$, and arranging all such columns neatly on the $x$-axis from left to right, starting from the origin.
Figure 1: The histogram from the first example test case and all three possible rectangles.
Given a histogram and a natural number $p$, determine the number of distinct rectangles $R$ such that: the vertices of $R$ are points with integer coordinates, one side of $R$ lies on the $x$-axis, the interior of $R$ is completely covered by the histogram, and the area of $R$ is at least $p$.
Input
The first line contains natural numbers $n$ and $p$ — the width of the histogram and the minimum allowed area of the rectangle. The next line contains $n$ natural numbers $h_1, h_2, \dots, h_n$ — the values of the distribution represented by the histogram.
Output
Print the required number of rectangles.
Subtasks
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | $1 \le n \le 3\,000, 1 \le p \le 10^{12}, 1 \le h_i \le 10^9$ |
| 2 | 15 | $1 \le n \le 100\,000, 1 \le p \le 10^8, 1 \le h_i \le 1\,000$ |
| 3 | 15 | $1 \le n \le 100\,000, p = 1, 1 \le h_i \le 10^9$ |
| 4 | 25 | $1 \le n \le 100\,000, 1 \le p \le 100\,000, 1 \le h_i \le 10^9$ |
| 5 | 35 | $1 \le n \le 100\,000, 1 \le p \le 10^{14}, 1 \le h_i \le 10^9$ |
Examples
Input 1
6 9 1 4 4 5 2 3
Output 1
3
Input 2
10 5 3 6 1 3 2 1 5 3 4 2
Output 2
31