直方图是统计分布的图形表示——该分布是一个函数，为 $1$ 到 $n$ 之间的每个整数 $j$ 分配一个特定的值 $h_j$。我们通过为每个数字 $j$ 绘制一个宽度为 $1$、高度为 $h_j$ 的矩形柱，并将所有这些矩形柱从左到右整齐地排列在 $x$ 轴上（从原点开始）来绘制直方图。
图 1：第一个样例数据对应的直方图以及所有三种可能的矩形。
给定一个直方图和一个正整数 $p$，确定满足以下条件的不同矩形 $R$ 的数量：$R$ 的顶点是具有整数坐标的点，$R$ 的一条边位于 $x$ 轴上，$R$ 的内部完全被直方图覆盖，且 $R$ 的面积至少为 $p$。
输入格式
第一行包含正整数 $n$ 和 $p$ — 直方图的宽度和矩形的最小允许面积。
下一行包含 $n$ 个正整数 $h_1, h_2, \dots, h_n$ — 直方图所表示的分布值。
输出格式
输出满足条件的矩形数量。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 | $1 \le n \le 3000$, $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 1000$ |
| 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$ |
样例
输入样例 1
6 9 1 4 4 5 2 3
输出样例 1
3
输入样例 2
10 5 3 6 1 3 2 1 5 3 4 2
输出样例 2
31