Rectangles in a Histogram

You are given a histogram on the Cartesian plane with width \(n\). For each \(1 \le i \le n\), the \(i\)th bar in the histogram is a rectangle with vertices \((i-1, 0)\), \((i, 0)\), \((i-1, h_i)\) and \((i, h_i)\), where \(h_i\) is a positive integer.

Given an integer \(p\), count the number of rectangles satisfying the following conditions:

• All four vertices of the rectangle have integer coordinates.
• One side of the rectangle lies on the \(x\)-axis.
• The rectangle is completely contained within the histogram (touching the boundary is allowed).
• The area of the rectangle is at least \(p\); that is, if the rectangle has width \(w\) and height \(y\) then \(w \times y \ge p\).

A rectangle that lies in the histogram can be defined by choosing two distinct vertical grid lines \(x=a\) and \(x=b\) (with \(0 \le a < b \le n\)) and a horizontal line \(y\) (with \(1 \le y \le \min\{h_{a+1}, h_{a+2}, \dots, h_b\}\)). The area of this rectangle is \((b-a)\times y\). Count all such rectangles that satisfy \((b-a)\times y \ge p\).

inputFormat

The first line contains two integers \(n\) and \(p\) where \(n\) is the number of bars in the histogram and \(p\) is the minimum area required.

The second line contains \(n\) integers \(h_1, h_2, \dots, h_n\) representing the height of each bar.

outputFormat

Output a single integer, the number of rectangles that satisfy the given conditions.

sample

3 1
1 2 3

10