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$).


-----Input-----

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$.


-----Output-----

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


-----Examples-----

Input
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
Output
81
3
1
2
0


-----Note-----

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]$.

Difficulty: HARD
Tags: Sorting

Data structures

Implementation

Complete search
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
from collections import defaultdict, OrderedDict
InputList = lambda Dtype: [Dtype(x) for x in input().split()]
import bisect

def solve():
	N = int(input())
	nums = InputList(int)
	n_zeros = bisect.bisect(nums, 0)
	nums = nums[n_zeros:]
	if not nums:
		return 0
	for _ in range(N - 1):
		diff = []
		if n_zeros:
			diff.append(nums[0])
			n_zeros -= 1
		for i in range(len(nums) - 1):
			cur = nums[i + 1] - nums[i]
			if cur:
				diff.append(cur)
			else:
				n_zeros += 1
		if not diff:
			return 0
		if len(diff) == 1:
			return diff[0]
		nums = sorted(diff)
ReturnMode = True
t = None
if not t:
	t = int(input())
if ReturnMode:
	for _ in range(t):
		ans = solve()
		if type(ans) == list:
			print(*ans)
		else:
			print(ans)
else:
	for _ in range(t):
		solve()


import sys
import math
T = int(sys.stdin.readline())

def remove_zeros(A):
	zeros = 0
	for a in A:
		if a == 0:
			zeros += 1
		else:
			break
	return (zeros, A[zeros:])

def solve(A):
	(zeros, A) = remove_zeros(A)
	while True:
		if A == []:
			return 0
		if len(A) == 1:
			return A[0]
		new_A = [A[i + 1] - A[i] for i in range(len(A) - 1)]
		if zeros > 0:
			new_A = [A[0]] + new_A
			zeros -= 1
		new_A.sort()
		(new_zeros, A) = remove_zeros(new_A)
		zeros += new_zeros
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	print(solve(A))


import bisect

def solve():
	n = int(input())
	g = list(map(int, input().split()))
	cnt = n - 1
	while cnt:
		cnt -= 1
		b = []
		for i in range(1, len(g)):
			b.append(g[i] - g[i - 1])
		b.sort()
		g = b[bisect.bisect(b, 0):]
		if len(g) <= cnt:
			g.insert(0, 0)
	print(g[0])
T = int(input())
for _ in range(T):
	solve()


for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = len([x for x in a if x == 0])
	a = [x for x in a if x > 0]
	while len(a) > 1:
		if c0 > 0:
			a.append(0)
			c0 -= 1
		a.sort()
		b = []
		for i in range(len(a) - 1):
			if a[i] == a[i + 1]:
				c0 += 1
			else:
				b.append(a[i + 1] - a[i])
		a = b[:]
	print(a[0] if len(a) > 0 else 0)


t = int(input())
while t:
	p = int(input())
	s = list(map(int, input().split()))
	check = 0
	while p > 1:
		a = []
		if check > 0:
			check -= 1
			a.append(s[0])
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				check += 1
			else:
				a.append(s[i] - s[i - 1])
		s = a
		if len(s) == 0:
			break
		s = sorted(a)
		p -= 1
	if len(s) == 0:
		print(0)
	else:
		print(s[0])
	t -= 1


import sys
input = sys.stdin.readline

def high_bound(arr, val):
	l = -1
	r = len(arr)
	while r - l > 1:
		m = (l + r) // 2
		if arr[m] <= val:
			l = m
		else:
			r = m
	return r
for _ in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	cnt = high_bound(a, 0)
	a = [0] * (cnt > 0) + a[cnt:]
	cnt = max(cnt - 1, 0)
	for i in range(n - 1, 0, -1):
		b = []
		for j in range(len(a) - 1):
			d = a[j + 1] - a[j]
			if d:
				b.append(d)
			else:
				cnt += 1
		if cnt:
			b.append(0)
			cnt -= 1
		b.sort()
		a = b
	print(b[0])


from bisect import bisect as b
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = l.copy()
	l.sort()
	for j in range(1, n):
		k = []
		for i in range(1, len(l)):
			k.append(l[i] - l[i - 1])
		k.sort()
		l = k[b(k, 0):]
		if len(l) < n - j:
			l.insert(0, 0)
	if len(l) == 1:
		print(l[0])


from bisect import bisect as b
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for j in range(1, n):
		k = []
		for i in range(1, len(l)):
			k.append(l[i] - l[i - 1])
		k.sort()
		l = k[b(k, 0):]
		if len(l) < n - j:
			l.insert(0, 0)
	if len(l) == 1:
		print(l[0])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	for j in range(1, n):
		k = []
		for i in range(1, len(l)):
			k.append(l[i] - l[i - 1])
		k.sort()
		l = k[k.count(0):]
		if len(l) < n - j:
			l.insert(0, 0)
	if len(l) == 1:
		print(l[0])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cz = 0
	while len(l) > 1:
		temp = list()
		for i in range(len(l) - 1):
			val = l[i + 1] - l[i]
			if val > 0:
				temp.append(val)
			else:
				cz += 1
		if cz > 0:
			temp.append(0)
			cz -= 1
		temp.sort()
		l = temp
	if len(l) == 0:
		print(0)
	else:
		print(l[0])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arrA = list(map(int, input().split()))
	arr = arrA.copy()
	arrA.sort()
	for j in range(1, n):
		k = []
		for i in range(len(arrA) - 1):
			k.append(arrA[i + 1] - arrA[i])
		k.sort()
		arrA = k[k.count(0):]
		if len(arrA) < n - j:
			arrA.insert(0, 0)
	if len(arrA) == 1:
		print(arrA[0])


from collections import Counter
for tcase in range(int(input())):
	n = int(input())
	a = list(Counter(map(int, input().split())).items())
	a.sort()
	while not (n == 1 or (len(a) == 2 and a[0][0] == 0)):
		b = Counter()
		for i in range(len(a) - 1):
			if a[i][1] > 1:
				b[0] += a[i][1] - 1
			b[a[i + 1][0] - a[i][0]] += 1
		if a[-1][1] > 1:
			b[0] += a[-1][1] - 1
		a = list(b.items())
		a.sort()
		n -= 1
	if len(a) > 1:
		print(a[1][0] - a[0][0])
	elif a[0][1] > 1:
		print(0)
	else:
		print(a[0][0])


from collections import defaultdict
t = int(input())
for jj in range(t):
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	dic = defaultdict(int)
	for i in p:
		dic[i] += 1
	while len(dic) > 1:
		dd = defaultdict(int)
		k = sorted(dic.keys())
		if dic[k[0]] > 1:
			dd[0] += dic[k[0]] - 1
		for i in range(1, len(k)):
			dd[k[i] - k[i - 1]] += 1
			if dic[k[i]] > 1:
				dd[0] += dic[k[i]] - 1
		dic = dd
	for a in dic.keys():
		if dic[a] == 1:
			ans = a
		else:
			ans = 0
	print(ans)