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-x|$ 的能量。这种能量是可以累加的，因此对某块瓷砖施加两次 $2$ 点能量，总共会施加 $4$ 点能量。请确定击碎所有瓷砖所需的最少击打次数。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $N$，表示瓷砖的数量。 第二行包含 $N$ 个空格分隔的整数 $p_0, p_1, \dots, p_{N-1}$，表示击碎第 $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

说明

对于第一个测试用例，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-6：$N \le 100$。
• 输入 7-14：无额外限制。