P12483 [集训队互测 2024] 人间应又雪

长度为 $n$ 的街道被积雪覆盖，将街道划分为 $n$ 段，第 $i$ 段的积雪量为 $a_i$，保证 $0\le a_i\le m$ 且 $a_i$ 为整数。 天依与言和要来清理积雪，每次清理有 $2$ 种选择。 + 天依从位置 $1$ 走到位置 $x$，将积雪清理掉 $c$，再走回位置 $1$，同时，因为在雪地上移动，位置 $1\sim x$ 的积雪量减少 $1$，即 $\forall i\in[1,x-1],a_i:=a_i-1,a_x:=a_x-c-1$。 + 言和从位置 $n$ 走到位置 $x$，将积雪清理掉 $c$，再走回位置 $n$，同时，因为在雪地上移动，位置 $x\sim n$ 的积雪量减少 $1$，即 $\forall i\in[x+1,n],a_i:=a_i-1,a_x:=a_x-c-1$。。 任意时刻，积雪量对 $0$ 取 $\max$。 天依与言和想知道，最少进行多少次清理后（**即最小化两人清理次数总和**），能将所有积雪清除，即 $\forall i\in [1,n],a_i=0$。

**本题有多组测试数据。** 首先输入一行两个数 $T,tid$，$T$ 表示数据组数，$tid$ 表示子任务编号（样例的子任务编号为 $0$）。 对于每组数据： 第一行三个整数 $n,m,c$。 第二行 $n$ 个整数 $a_{1\sim n}$。

对于每组数据，输出一行一个整数表示答案。

### 样例解释 1 天依走到位置 $4$ 清理，积雪量变为 $[0,2,1,1,1]$。 言和走到位置 $2$ 清理，积雪量变为 $[0,0,0,0,0]$。 共 $2$ 次清理。 ### 样例解释 2 见附加文件中的 `snow.in` 与 `snow.ans`。 这个样例中有 $100$ 组 $n=10,m=10$ 的数据。 ### 数据范围 对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 5\times 10^5$，$\sum n,\sum m\le 10^6$，$0\le a_i\le m$，$0\le c\le 5\times 10^5$。 | 子任务编号 | $n$ | $m$ | 特殊限制 | 分值 | 子任务依赖 | | :--------: | :----------------: | :----------------: | :-----------------------------: | :--: | :--------: | | $1$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | $c=0$ | $2$ | | | $2$ | $\le 5\times 10^5$ | $\le 2$ | 无 | $3$ | | | $3$ | $\le 5$ | $\le 5$ | $T\le 10$ | $5$ | | | $4$ | $\le 50$ | $\le 50$ | $\sum n,\sum m\le 200$ | $10$ | $3$ | | $5$ | $\le 300$ | $\le 300$ | $\sum n,\sum m\le 600$ | $10$ | $4$ | | $6$ | $\le 2000$ | $\le 2000$ | $\sum n,\sum m\le 4000$ | $10$ | $5$ | | $7$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | $c\le 20,\sum n,\sum m\le 10^5$ | $20$ | | | $8$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | $\sum n,\sum m\le 10^5$ | $15$ | $6,7$ | | $9$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | $c\le 20$ | $10$ | $1,7$ | | $10$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | 无 | $15$ | $2,8,9$ |