题目描述

译自 ROI 2024 Day2 T4. За связь без перебоев

在一条进行无人驾驶卡车试验的直线道路上，有 $n$ 个城市，第 $i$ 个城市位于坐标点 $i$。在第 $i$ 个城市安装了一台功率为 $a_i$ 的天线，可以覆盖从 $L_i = \max(1, i - a_i)$ 到 $R_i = \min(n, i + a_i)$ 的所有城市。

无人驾驶卡车从城市 $s$ 开始，沿着道路移动到城市 $t$，其中 $s < t$。卡车在经过的每个城市都会连接到覆盖该城市的某个天线。天线的连接方式如下：

• 在起始城市 $s$，卡车连接到覆盖该城市且 $R_i$ 值最大的天线。如果有多个这样的天线，可以选择任意一个。
• 当卡车从城市 $v$ 移动到 $v+1$ 时，如果之前连接的天线也覆盖城市 $v+1$，则卡车保持连接不变。否则，如果之前的天线不覆盖城市 $v+1$，卡车将重新连接到覆盖城市 $v+1$ 且 $R_i$ 值最大的天线。如果有多个这样的天线，可以选择任意一个。

定义 $f(s, t)$ 为卡车从城市 $s$ 开始，到城市 $t$ 结束的路途中发生的天线重新连接次数（不包括在城市 $s$ 的初始连接）。

将天线覆盖道路的不稳定性定义为所有有效城市对的 $f(s, t)$ 值之和，即

道路运营商手中有一台备用天线，功率为 $x$。为了减少覆盖不稳定性，可以选择用这台备用天线替换任意一台现有的天线。任务是确定如果最多替换一台天线，道路的覆盖不稳定性 $F$ 的最小可能值。

输入格式

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

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

输出格式

输出一个整数，表示如果最多替换一台天线，道路的覆盖不稳定性 $F$ 的最小可能值。

3 1
1 0 0

0

在第一个样例中，我们可以将第二个天线替换为备用天线。这样，从任何起始点开始的卡车都将连接到它，并且不需要重新连接到任何其他天线。

5 0
2 1 0 0 1

6

在第二个样例中，不需要使用备用天线。从前三个城市出发到最后两个城市的卡车必须重新连接到最后一个天线一次，因此道路的覆盖不稳定性为 $6$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。