P11303 [NOISG 2021 Finals] Pond

乌龟 Syrup 经常在他家旁边的池塘里游泳。这个池塘是由很久以前的冰川运动形成的，呈狭长直线状，水面平静，适合双向游泳。

今天，Syrup 像往常一样游泳时，发现了一簇绿点——正在萌发的藻类孢子。经过暴雨冲刷，富含营养的土壤流入池塘，为藻类提供了大量养分，导致它们以惊人的速度生长。如果不加以控制，这些藻类会遮挡阳光，破坏水下生态平衡。 幸运的是，Syrup 有一个简单有效的解决方案——吃掉它们。他已经识别出池塘中 $N$ 个土壤流失点，标号为 $1$ 到 $N$，并记下了它们之间的距离 $D_i$（第 $i$ 点到第 $i+1$ 点之间的距离为 $D_i$）。目前，Syrup 位于第 $K$ 个点，并从这里开始消灭藻类。 池塘中的每个点初始有 $0$ 条藻类，并且每秒会增加 $1$ 条藻类，直到 Syrup 到达该点并吃掉所有藻类。Syrup 需要选择一个方向，沿着池塘游泳，并依次吃掉遇到的所有藻类。为了让藻类不至于变得太难吃，他希望尽可能减少吃下的藻类总数。 你的任务是计算 Syrup 吃下的最少藻类总数。

- 第一行包含两个整数 $N$ 和 $K$，分别表示池塘中的土壤流失点数量和 Syrup 的起始位置。 - 第二行包含 $N-1$ 个整数 $D_1, D_2, \dots, D_{N-1}$，表示相邻流失点之间的距离。

输出一个整数，表示 Syrup 吃下的最少藻类总数。

【样例解释】 - 对于样例 $1$，最优路径是按顺序访问点 $3 \to 2 \to 4 \to 5 \to 6 \to 7 \to 1$，总共吃掉 $0 + 2 + 8 + 10 + 12 + 17 + 37 = 86$ 条藻类。 - 对于样例 $2$，最优路径是按顺序访问点 $5 \to 6 \to 4 \to 3 \to 2 \to 1 \to 7 \to 8 \to 9$，总共吃掉 $0 + 1 + 3 + 5 + 8 + 12 + 26 + 32 + 42 = 129$ 条藻类。 - 对于样例 $3$，最优路径是按顺序访问点 $4 \to 3 \to 2 \to 1 \to 5 \to 6$，总共吃掉 $0 + 1 + 2 + 3 + 7 + 8 = 21$ 条藻类。 【数据范围】 - $2 \leq N \leq 3 \times 10^5$ - $1 \leq K \leq N$ - $1 \leq D_i \leq 10^6$ | 子任务编号 | 分值 | 额外限制条件 | | :--------: | :--: | :-------------------------------: | | $1$ | $7$ | $N \leq 100$ | | $2$ | $11$ | $N \leq 2000$ | | $3$ | $10$ | $1 \leq K \leq \min(N, 20)$ | | $4$ | $6$ | $D_i = 1$ | | $5$ | $12$ | $1 \leq K \leq \min(N, 2000)$ 且 $D_i \geq D_{i+1}$（对所有 $i$ 满足 $i \not\equiv 0 \pmod{100}$） | | $6$ | $25$ | $1 \leq K \leq \min(N, 2000)$ | | $7$ | $29$ | 无额外限制 |