题目背景

题目描述

Alek 岁在某知名 OJ 代码力量上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 公差非正 的等差数列，这样画出来的统计图表很好看。

尽管 Alek 岁一天能做 42 道题，但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。

你可以认为 OJ 上有足够多的各种难度的题目。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

• 第一行一个整数 $n$ 表示难度总数。
• 第二行 $n$ 个整数 $a_i$。

输出格式

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

6
2
822 1064
2
1064 822
4
1 3 4 2
4
2 4 3 1
6
2 6 2 1 4 4
9
9 9 8 2 4 4 3 5 3

242
0
6
4
17
25

提示

对于所有数据，$1\leq T\leq 100$，$1\leq n, \sum n\leq 10 ^ 5$，$1\leq a_i\leq 10 ^ 9$。

• 子任务 1（$30$ 分）：$\sum n \leq 10 ^ 3$。
• 子任务 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 L by Alex_Wei