题目描述

译自 CEOI2018 Day1 T2. Global Warming

全球气候变暖是一个非常严峻的问题，Johnny 对此深有体会。他决定对历史温度数据进行分析，找到温度严格上升的子序列。他想借此说服那些不相信全球气候变暖的人！

Johnny 找到了连续 $n$ 天的历史数据，第 $i$ 天的气温为 $t_i$。

为了让温度最长严格上升子序列变得更长一些，他决定对原始数据做点手脚。在找出一个非空区间 $[l,r]$ 和一个整数 $d\ (-x \leq d \leq x)$ 后，他将会把 $t_l,t_{l+1},\ldots ,t_r$ 全部加上 $d$（$d=0$ 也是允许的）。

在经过这样一次修改操作后，整个序列的最长严格上升子序列的最大可能长度是多少？

输入格式

第一行两个整数 $n,x$，分别代表数据包含的天数和允许改变温度的限值。

第二行 $n$ 个整数 $t_1,t_2,\ldots ,t_n$，即原始的温度数列。

输出格式

输出一个整数，即经过修改操作后最长严格上升子序列的最大可能长度。

样例

8 10
7 3 5 12 2 7 3 4

5

将 $[2,3]$ 中的所有数同时加上 $-5$ 之后，得到的新序列为 $7,−2,0,12,2,7,3,4$，该序列的最长上升子序列为 $−2,0,2,3,4$，长度为 $5$。

数据范围与提示

所有数据均满足 $1 \leq n \leq 200\,000$，$0 \leq x \leq 10^9$，$1 \leq t_i \leq 10^9$。