题目描述

Bessie 正在试验一种能够产生巨大冲击波的强大的蹄部植入物。她有 $N$（$2 \leq N \leq 10^5$）块砖块排开在面前，分别需要至少 $p_0,p_1,\dots,p_{N-1}$ 的力量才能击破（$0 \leq p_i \leq 10^{18}$）。

Bessie 可以通过击打特定的砖块来施加力量，但由于她的植入物的奇特性质，它不会对她所击打的那块砖块施加任何力量。相反，如果她选择击打砖块 $x$ 一次，其中 $x$ 是一个 $[0,N-1]$ 范围内的整数，对所有在 $[0,N-1]$ 范围内的整数 $i$，它将对砖块 $i$ 施加 $|i-x|$ 的力量。同时这个力量是累积的，因此对一块砖块施加两次 $2$ 的力量将对该砖块施加总共 $4$ 的力量。

请求出击破所有砖块所需要的最少击打次数。

输入格式

输入的第一行包含 $T$（$1 \leq T \leq 100$），为测试用例的数量。

第 $2t$ 行包含一个整数 $N$，为测试用例 $t$ 中的砖块数量。

第 $2t+1$ 行包含 $N$ 个空格分隔的整数 $p_0,p_1, \ldots, p_{N-1}$，表示砖块 $i$ 需要 $p_i$ 的力量才能击破。

输入保证一个测试点中的所有 $N$ 之和不超过 $5\cdot 10^5$。

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

2
3
2
4
4
2000000000000000000

提示

样例 1 解释：

在第一个测试用例中，Bessie 通过两次击打击破所有砖块的唯一方法是击打砖块 $0$ 两次，施加总力量分别为 $[0,2,4,6,8]$。

在第二个测试用例中，Bessie 通过三次击打击破所有砖块的一种方法是分别击打砖块 $0$，$2$ 和 $4$ 一次，施加总力量分别为 $[6,5,4,5,6]$。

在第三个测试用例中，Bessie 通过两次击打击破所有砖块的一种方法是分别击打砖块 $0$ 和 $1$ 一次，施加总力量分别为 $[1,1,3,5,7]$。

• 测试点 $2$：所有 $p_i$ 均相等。
• 测试点 $3\sim 6$：$N\le 100$。
• 测试点 $7\sim 14$：没有额外限制。