P11261 [COTS 2018] 直方图 Histogram
题目背景
译自 [Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2018/) D1T1。$\texttt{1s,1G}$。
题目描述
给定笛卡尔坐标系中的直方图，宽度为 $n$，第 $i$ 格的高度为 $h_i$。也就是说，对于 $\forall 1\le i\le n$，第 $i$ 格所占矩形的顶点坐标分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$。
给定正整数 $p$，求出满足以下条件的矩形的数量：
- 矩形的四个顶点的坐标均为整数；
- 矩形有一条边在 $x$ 轴上；
- 矩形完全位于直方图内部（可以与边界相切）；
- 矩形的面积至少为 $p$。
输入格式
第一行，两个正整数 $n,p$。
第二行，$n$ 个正整数 $h_1,h_2,\ldots,h_n$。
输出格式
输出一行一个整数，表示答案。
说明/提示
#### 样例解释
样例一解释：
#### 数据范围
对于 $100\%$ 的数据，保证：
- $1\le n\le 10^5$；
- $1\le p\le 10^{14}$；
- $1\le h_i\le 10^{9}$。
| 子任务编号 | $n\le $ | $p$ | $h_i\le$ | 得分 |
| :--: | :--: | :--: | :--: | :--: |
| $ 1 $ | $ 3\, 000 $ | $\le 10^{12}$ | $ 10^9$ | $ 10 $ |
| $ 2 $ | $ 10^5 $ | $\le 10^8$ | $1\, 000$ | $ 15 $ |
| $ 3 $ | $ 10^5$ | $=1$ | $10^9$ | $ 15 $ |
| $ 4 $ | $ 10^5$ | $\le 10^5$ | $10^9$ | $ 25 $ |
| $ 5 $ | $ 10^5$ | $\le 10^{14}$ | $10^9$ | $ 35 $ |