题目内容

一条质检线上依次排出 $n$ 件工件，第 $i$ 件的质量读数为 $q_i$，另有非负整数公差 $t$。

对每个满足 $1 \le i \le n-2$ 的下标 $i$，把连续三件 $\{q_i,q_{i+1},q_{i+2}\}$ 看成一个候选抽检组。若

则该抽检组合格。

可以选用任意多个合格抽检组，也可以一个都不选。被选用的抽检组两两不能占用同一件工件。求最多能选出多少个合格抽检组。

输入描述

第一行两个整数 $n$ 和 $t$（$1 \le n \le 2 \times 10^5$；$0 \le t \le 10^9$），表示工件数量与公差。

第二行 $n$ 个整数 $q_1,q_2,\dots,q_n$（$0 \le q_i \le 10^9$），表示各工件的质量读数。

输出描述

输出一个整数，即最多能选出的合格抽检组个数。

样例1

输入

10 5
10 12 8 15 11 14 20 22 19 3

输出

3

说明

可以选用下标 $1,2,3$、$4,5,6$、$7,8,9$ 三个抽检组。它们互不占用同一工件，且每组内最大值与最小值之差都不超过 $5$。第 $10$ 件无法再组成抽检组。

样例2

输入

8 0
4 4 4 4 2 2 2 9

输出

2

说明

可以选用下标 $1,2,3$ 与 $5,6,7$ 两个抽检组。公差为 $0$ 时组内三个读数必须相同；最后一件读数为 $9$ 的工件无法单独成组。