A90524.「USACO 2025.1 Platinum」Shock Wave

题目来自 USACO 2025 January Contest, Platinum Problem 2. Shock Wave

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$ 个测试用例的答案。