传统题 2000ms 256MiB

Time Limit Exceeded

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个由n个非负整数组成的数组a。保证a是从小到大排序的。

对于每个操作,我们生成一个新数组bi=ai+1aib_i=a_{i+1}-a_i,1≤i<n。然后我们把b从小到大排序,用b替换a,并把n减少1。

在进行了n-1次操作后,n变成了1。你需要输出数组a中唯一的整数(也就是说,你需要输出a1a_1)。

Format

Input

输入由多个测试案例组成。第一行包含一个整数t(1t1041\leq t \leq10^4 )--测试案例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n(2n1052\leq n \leq10^5 )--数组a的长度。

第二行包含n个整数a1a_1,a2a_2,...,ana_n0a1...an51050\leq a_1\leq...\leq a_n\leq5⋅10^5)--数组a。

保证每个测试案例的n之和不超过2.51052.5⋅10^5

Output

对于每个测试案例,在新的一行中输出答案。

Samples

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

样例解释

sort(a)表示将a从小到大排序后得到的数组。

在第一个测试案例中,一开始a=[1,10,100]。第一次操作后,a=sort([10-1,100-10])=[9,90]。第二次操作后,a=sort([90-9])=[81]。

在第二个测试案例中,起初a=[4,8,9,13]。第一次操作后,a=sort([8-4,9-8,13-9])=[1,4,4]。第二次操作后,a=sort([4-1,4-4])=[0,3]。最后一次操作后,a=sort([3-0])=[3]。

2022ACM新生积分赛 Round #3

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2022-10-29 13:00
结束于
2022-10-29 18:00
持续时间
5 小时
主持人
参赛人数
70