Maria Petrovna 是大学老师。期中测试有 $n$ 道题，按难度递增排列。

她知道每个学生属于以下三类之一：

1. 勤奋学生：从最简单的题开始，按难度递增连续做题，直到时间结束；
2. 聪明学生：从最难的题开始，按难度递减连续做题，直到时间结束；
3. 差学生：恰好从某个勤奋学生或聪明学生那里抄一题。并且两个差学生不能从同一个人那里抄同一道题。

勤奋学生和聪明学生会正确完成自己来得及做的所有题。如果老师发现抄袭，那么抄袭者和被抄者这道题都不计分。

测试结束后，老师原本记录了每个学生被计分的题目，但后来这份名单丢了，只留下了每道题被多少名学生计分的数量 $a_i$。

请你求出，在这些统计数据可能成立的前提下，差学生数量的最小值。

输入格式

第一行包含整数 $T$，表示测试组数。

每组测试包含两行：第一行包含整数 $n$，表示题目数量；第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每道题被计分的学生数。

约束：$0\le a_i\le 10^9$，所有测试中 $n$ 的总和不超过 $10^5$，且每组至少有一道题。

输出格式

对每组测试输出一行一个整数，表示最少可能有多少个差学生。

样例输入

2
4
3 2 0 1
3
1 5 1

样例输出

0
3

样例说明

第一组可以由若干勤奋学生和聪明学生解释，不需要差学生。

第二组中，可以有若干勤奋/聪明学生，再加上 $3$ 个差学生分别抄第一题，导致相应计分被取消，最终得到统计数组。