题目描述

一条笔直道路上有 $n$ 个城市，第 $i$ 个城市位于坐标 $i$。第 $i$ 个城市安装了一座功率为 $a_i$ 的天线，它覆盖的城市编号区间为：

一辆无人驾驶卡车从城市 $s$ 行驶到城市 $t$，其中 $s<t$。在路径上的每个城市，卡车都会连接到某一座覆盖当前城市的天线。连接规则如下：

• 在起点城市 $s$，卡车连接到一座覆盖 $s$ 的天线，并要求该天线的 $R_i$ 最大；若有多座满足条件的天线，可任选其一。
• 当卡车从城市 $v$ 前进到城市 $v+1$ 后，若当前连接的天线也覆盖城市 $v+1$，则保持连接；否则，卡车切换到一座覆盖 $v+1$ 且 $R_i$ 最大的天线；若有多座满足条件的天线，可任选其一。

令 $f(s,t)$ 表示从 $s$ 到 $t$ 的过程中发生的天线切换次数。起点处的初始连接不计为切换。

定义整条道路通信覆盖的不稳定度为：

运营商有一座备用天线，功率为 $x$。为了降低不稳定度，可以选择至多一座现有天线，并将其替换为这座功率为 $x$ 的备用天线。

请输出替换至多一座天线后，可能得到的最小不稳定度 $F$。

输入格式

第一行包含两个整数 $n,x$，分别表示城市数量和备用天线功率。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各城市现有天线的功率。

输出格式

输出一个整数，表示替换至多一座天线后道路通信覆盖不稳定度的最小可能值。

数据范围

• $1\le n\le 10^6$；
• $0\le x\le n$；
• $0\le a_i\le n$。

子任务

样例 1

输入

3 1
1 0 0

输出

0

说明

可以将第二座天线替换为备用天线。这样任意起点出发的卡车都可以一直连接到它，不需要发生切换。

样例 2

输入

5 0
2 1 0 0 1

输出

6

说明

最优方案是不使用备用天线。对于从前三个城市之一出发、到达最后两个城市之一的路线，卡车都需要切换到最后一座天线一次，因此不稳定度为 $6$。