题目描述

长度为 $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 0
5 5 1
1 3 2 3 1

2

提示

样例解释 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$。