沿一条直线道路分布着 $n$ 个城市，第 $i$ 个城市位于坐标 $i$ 处。第 $i$ 个城市安装有一台功率为 $a_i$ 的天线，覆盖范围为从 $L_i = \max(1, i - a_i)$ 到 $R_i = \min(n, i + a_i)$（包含端点）。

无人驾驶货车沿道路从城市 $s$ 行驶至城市 $t$（其中 $s < t$）。在行驶路径上的每个城市，货车都会连接到其中一台天线。连接规则如下：

• 在起始城市，货车连接到覆盖该城市且 $R_i$ 值最大的天线。若存在多台这样的天线，则任选其一。
• 当货车从城市 $v$ 移动到城市 $v+1$ 时，如果货车在城市 $v$ 连接的天线也覆盖城市 $v+1$，则货车保持连接。否则，如果当前连接的天线不覆盖城市 $v+1$，货车将重新连接到覆盖城市 $v+1$ 且 $R_i$ 值最大的天线。若存在多台这样的天线，则任选其一。

设 $f(s, t)$ 为货车从城市 $s$ 出发到达城市 $t$（$s < t$）过程中，天线切换的次数。在城市 $s$ 的初始连接不计入切换次数。

我们将道路覆盖的不稳定性定义为所有合法城市对的 $f(s, t)$ 之和，即： $$F = \sum_{s=1}^{n-1} \sum_{t=s+1}^{n} f(s, t)$$

道路运营商拥有一台功率为 $x$ 的备用天线。为了降低覆盖的不稳定性，可以将其中一台天线替换为备用天线。请计算在最多替换一台天线的情况下，道路覆盖不稳定性 $F$ 的最小值。

输入格式

第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 10^6$，$0 \le x \le n$），分别表示城市数量和备用天线的功率。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$），表示各天线的功率。

输出格式

输出在最多替换一台天线的情况下，道路覆盖不稳定性的最小值。

子任务

样例

样例输入 1

3 1
1 0 0

样例输出 1

0

样例输入 2

5 0
2 1 0 0 1

样例输出 2

6

说明

在第一个样例中，我们可以将第二台天线替换为备用天线。这样，从任意点出发的货车都会连接到该天线，无需进行任何切换。

在第二个样例中，无需使用备用天线。对于从前三个城市中任一城市出发，并到达最后两个城市中任一城市的货车，都需要切换一次到最后一台天线，因此道路覆盖的不稳定性为 6。