P11119 [ROI 2024] 保持连接 (Day 2)

翻译自 [ROI 2024 D2T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。 在一条进行无人驾驶卡车测试的直路上，有 $n$ 个城市，第 $i$ 个城市位于坐标为 $i$ 的位置。第 $i$ 个城市安装了一个功率为 $a_i$ 的天线，覆盖从 $L_i = \max(1, i - a_i)$ 到 $R_i = \min(n, i + a_i)$ 的所有城市。 无人驾驶卡车沿着这条路从城市 $s$ 移动到城市 $t$，其中 $s < t$。卡车在经过的每个城市都会连接到覆盖该城市的某个天线。连接天线的规则如下： 1. 在起始城市，卡车连接到覆盖该城市的天线中 $R_i$ 最大的一个。如果有多个这样的天线，可以选择其中任何一个。 2. 当卡车从城市 $v$ 移动到城市 $v + 1$ 时，如果之前连接的天线仍覆盖城市 $v + 1$，卡车将继续连接到该天线。否则，如果之前连接的天线不再覆盖城市 $v + 1$，卡车将重新连接到覆盖城市 $v + 1$ 的天线中 $R_i$ 最大的一个。如果有多个这样的天线，可以选择其中任何一个。 我们用 $f(s, t)$ 表示从城市 $s$ 到城市 $t$ 的卡车在途中进行的天线重新连接的次数（$s < t$）。在城市 $s$ 进行的初次连接不算作重新连接。

定义天线覆盖道路的不稳定性 $F$ 为 $f(s, t)$ 的总和，即： $$F = \sum_{s=1}^{n-1} \sum_{t=s+1}^{n} f(s, t)$$ 道路运营商有一个备用天线，功率为 $x$。为了降低天线覆盖的不稳定性，可以用备用天线替换任意一个现有天线。你需要确定，如果最多替换一个天线为功率 $x$ 的备用天线，不稳定性 $F$ 值最小可能是多少。

第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 10^6$，$0 \leq x \leq n$），分别为城市的数量和备用天线的功率。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq n$），即每个城市天线的功率。

输出在最多用一个备用天线替换现有天线后，$F$ 的最小可能值。

在第一个样例中，可以将第二个天线替换为备用天线。这样，卡车从任何位置出发，都会连接到备用天线，避免了任何重新连接。 在第二个样例中，不需要使用备用天线。所有从前 $3$ 个城市出发且到达最后 $2$ 个城市的卡车，都需要重新连接到最后一个天线，因此不稳定性总和为 $6$。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $7$ | $n\le100$ | | $2$ | $8$ | $n\le500$ | | $3$ | $6$ | $n\le5000$ | | $4$ | $12$ | $x=0$ | | $5$ | $5$ | $a_i=0$ | | $6$ | $16$ | $a_i\le1$ | | $7$ | $14$ | $a_i\ge\frac n{20}$ | | $8$ | $32$ | 无 | 全部数据范围见输入格式。