Difference Array

### 题目描述 你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。 显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。 ### 输入格式 输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。 对于每一组数据： - 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度 - 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。 ### 输出格式 $t$ 行，每行一个正整数，表示每一组数据中 $a$ 数组最终剩下的那个元素。 ### 样例解释 令 $\operatorname{sort}(a)$ 表示将 $a$ 数组从小到大排序。 - 对于第一组数据，初始的 $a = \{1,10,100\}$；在第一次操作后，$a=\operatorname{sort}(\{10-1,100-10\})=\{9,90\}$；在第二次操作后，$a = \operatorname{sort}(\{90-9\})=\{81\}$。故答案为 $81$。 - 对于第二组数据，初始的 $a=\{4,8,9,13\}$；在第一次操作后，$a=\operatorname{sort}(\{8-4,9-8,13-9\})=\{1,4,4\}$；在第二次操作后，$a=\operatorname{sort}(\{4-1,4-4\})=\{0,3\}$；在第三次操作后，$a=\operatorname{sort}(\{3-0\})=\{3\}$。故答案为 $3$。

You are given an array $ a $ consisting of $ n $ non-negative integers. It is guaranteed that $ a $ is sorted from small to large. For each operation, we generate a new array $ b_i=a_{i+1}-a_{i} $ for $ 1 \le i < n $ . Then we sort $ b $ from small to large, replace $ a $ with $ b $ , and decrease $ n $ by $ 1 $ . After performing $ n-1 $ operations, $ n $ becomes $ 1 $ . You need to output the only integer in array $ a $ (that is to say, you need to output $ a_1 $ ).

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 2\le n\le 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1,a_2,\dots,a_n $ ( $ 0\le a_1\le \ldots\le a_n \le 5\cdot 10^5 $ ) — the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2.5\cdot 10^5 $ , and the sum of $ a_n $ over all test cases does not exceed $ 5\cdot 10^5 $ .

For each test case, output the answer on a new line.

5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0

81
3
1
2
0

To simplify the notes, let $ \operatorname{sort}(a) $ denote the array you get by sorting $ a $ from small to large. In the first test case, $ a=[1,10,100] $ at first. After the first operation, $ a=\operatorname{sort}([10-1,100-10])=[9,90] $ . After the second operation, $ a=\operatorname{sort}([90-9])=[81] $ . In the second test case, $ a=[4,8,9,13] $ at first. After the first operation, $ a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4] $ . After the second operation, $ a=\operatorname{sort}([4-1,4-4])=[0,3] $ . After the last operation, $ a=\operatorname{sort}([3-0])=[3] $ .