题目背景

小铃最近新买了一堆磁正方体。

题目描述

小铃将正方体放在一个平面上，每个正方体的边长均为 $1$。将这个平面建成一个平面直角坐标系，那么沿着 $x$ 轴和 $y$ 轴各有一道零宽度而无限长的障碍，小铃只会将正方体平行于坐标轴的放在该坐标系的第一象限。我们可以用正方体的左下角坐标来标识一个正方体。

对于同一个 $x$ 坐标的正方体，小铃一定会将这些正方体放在尽量低的地方。当 $x$ 坐标为 $i$，有 $a _ i$ 个正方体时，这些正方体的坐标分别为 $(i, 0), (i, 1), \ldots, (i, a _ i - 1)$。

初始时，只有前 $n$ 个 $x$ 坐标上有正方体，$x$ 坐标为 $i$ 时的正方体个数为 $a _ i$。小铃可以减少一些 $x$ 坐标上的正方体数量，但她不能改变某个正方体的 $x$ 坐标。

当所有正方体摆出来之后，其图案关于直线 $y = x$ 对称时，小铃才会喜欢这样的摆放。请你帮助小铃计算最少需要减少多少个正方体，才能使得所有正方体摆放出来的图案关于直线 $y = x$ 对称。

输入格式

本题有多组测试数据。第一行一个正整数 $T$，表示测试数据数量。

对于每组测试数据，第一行一个正整数 $n$，表示初始时只有前 $n$ 个 $x$ 坐标上有正方体。 接下来一行 $n$ 个正整数 $a _ i$，表示 $x$ 坐标为 $i$ 时的正方体个数。

输出格式

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

样例

样例输入 1

3
6
6 6 4 4 1 1 
6
6 5 5 2 2 1 
6
5 3 2 2 1 1

样例输出 1

2
2
2

样例 1 解释

• 对于第一组数据，可以将 $a$ 数组改为 $\{6, 4, 4, 4, 1, 1\}$，不难发现这样是对称的。
• 对于第二组数据，可以将 $a$ 数组改为 $\{6, 5, 3, 2, 2, 1\}$，不难发现这样是对称的。
• 对于第三组数据，可以将 $a$ 数组改为 $\{5, 3, 2, 1, 1, 0\}$，不难发现这样是对称的。

样例输入/输出 2

见下发文件 cube2.in/ans。该样例满足测试点 $4 \sim 5$ 的限制。

样例输入/输出 3

见下发文件 cube3.in/ans。该样例满足测试点 $9 \sim 10$ 的限制。

数据范围与提示

本题共 $10$ 个测试点，每个测试点 $10$ 分。

特殊性质 A：保证 $a _ i \ge a _ {i + 1}$。

对于所有数据，$1 \le n \le 10 ^ 5$，$1 \le a _ i \le 10 ^ 9$，$1 \le T \le 20$。