This problem is a complicated version of D1, but it has significant differences, so read the whole statement.

Polycarp has an array of $n$ ($n$ is even) integers $a_1, a_2, \dots, a_n$. Polycarp conceived of a positive integer $k$. After that, Polycarp began performing the following operations on the array: take an index $i$ ($1 \le i \le n$) and reduce the number $a_i$ by $k$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $k$ at which such a situation is possible, or print $-1$ if such a number can be arbitrarily large.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of two lines. The first line contains an even integer $n$ ($4 \le n \le 40$) ($n$ is even). The second line contains $n$ integers $a_1, a_2, \dots a_n$ ($-10^6 \le a_i \le 10^6$).

It is guaranteed that the sum of all $n$ specified in the given test cases does not exceed $100$.


-----Output-----

For each test case output on a separate line an integer $k$ ($k \ge 1$) — the maximum possible number that Polycarp used in operations on the array, or $-1$, if such a number can be arbitrarily large.


-----Examples-----

Input
4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1
Output
13
2
-1
-1


-----Note-----

None

Difficulty: HARD
Tags: Number theory

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
import math
memo = {}

def divisors(n):
	if n in memo:
		return memo[n]
	divs = [1]
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			divs.extend([i, int(n / i)])
	divs.extend([n])
	memo[n] = list(set(divs))
	return memo[n]
for t in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	mxK = 0
	for j in nums:
		diff = [x - j for x in nums]
		k = max(diff)
		cnt = diff.count(0)
		if cnt >= n / 2:
			mxK = -1
			break
		cnt_div = {}
		for i in diff:
			if i > 0:
				divs = divisors(i)
				for d in divs:
					cnt_div[d] = cnt_div.get(d, 0) + 1
		cnt_div = sorted(cnt_div.items(), reverse=True)
		for (u, v) in cnt_div:
			if v + cnt >= n / 2:
				mxK = max(mxK, u)
	print(mxK if mxK > 0 else -1)


import math

def half_the_same(n, a):
	best_divisor = float('-inf')
	a.sort()
	if a[0] == a[-1]:
		return -1
	for i in range(n // 2 + 1):
		if i >= 1 and a[i] == a[i - 1]:
			for divisor in counts_by_divisor:
				counts_by_divisor[divisor] += 1
			counts_by_divisor[float('inf')] -= 1
		else:
			counts_by_divisor = {}
			for j in range(i + 1, n):
				diff = a[j] - a[i]
				for divisor in get_divisors(diff):
					if divisor in counts_by_divisor:
						counts_by_divisor[divisor] += 1
					else:
						counts_by_divisor[divisor] = 1
		for (divisor, count) in counts_by_divisor.items():
			if count >= n // 2 - 1:
				if divisor > best_divisor:
					best_divisor = divisor
		if best_divisor == float('inf'):
			return -1
	return best_divisor

def get_divisors(value):
	if value == 0:
		yield float('inf')
		return
	m = int(math.ceil(math.sqrt(value)))
	for d in range(1, m + 1):
		if value % d == 0:
			e = value // d
			if d < e:
				yield d
				yield e
			elif d == e:
				yield d
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	print(half_the_same(n, a))


def solve():
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	d = dict()
	temp = 0
	for x in arr:
		d[x] = d[x] + 1 if x in d else 1
		temp = max(temp, d[x])
	if temp >= n // 2:
		print(-1)
		return
	ans = 0
	prev = None
	for i in range(n // 2 + 1):
		if arr[i] == prev:
			continue
		prev = arr[i]
		diff = [abs(arr[i] - arr[j]) for j in range(i + 1, n)]
		factors = dict()
		factors[1] = 0
		add = 0
		for x in diff:
			if x == 0:
				add += 1
				continue
			y = 1
			while y * y <= x:
				if x % y == 0:
					if y in factors:
						factors[y] += 1
					else:
						factors[y] = 1
					if y != x // y:
						if x // y in factors:
							factors[x // y] += 1
						else:
							factors[x // y] = 1
				y += 1
		for x in factors:
			if factors[x] + add + 1 >= n // 2:
				ans = max(ans, x)
	print(ans)
for _ in range(int(input())):
	solve()


T = int(input())

def find(N):
	res = set([])
	i = 1
	while i * i <= N:
		if N % i == 0:
			res.add(i)
			res.add(N // i)
		i += 1
	return res
for t in range(T):
	ans = 0
	N = int(input())
	A = list(map(int, input().split()))
	K = -1
	for i in range(N):
		min_val = A[i]
		same = 0
		divs = []
		for j in range(N):
			if A[j] == min_val:
				same += 1
			elif A[j] > min_val:
				divs.append(A[j] - min_val)
		if same >= N // 2:
			K = float('inf')
			continue
		umap = {}
		for div in divs:
			for di in find(div):
				umap[di] = umap.get(di, 0) + 1
		for key in umap:
			if umap[key] >= N // 2 - same:
				K = max(K, key)
	ans = -1 if K == float('inf') else K
	print(ans)


import math
from collections import Counter
from math import gcd, floor, sqrt

def divs(n: int):
	d = set()
	for div in range(1, floor(sqrt(n)) + 1):
		if n % div == 0:
			d.add(div)
			d.add(n // div)
	return d
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	candidates = []
	k = -1
	for i0 in range(n):
		numberOfAi0Value = 0
		d = []
		for i in range(n):
			if a[i] == a[i0]:
				numberOfAi0Value += 1
			elif a[i] > a[i0]:
				d.append(a[i] - a[i0])
		if numberOfAi0Value >= n // 2:
			k = math.inf
			continue
		div_counter = Counter()
		for ai in d:
			for div in divs(ai):
				div_counter[div] += 1
		for p in div_counter.most_common():
			if p[1] >= n // 2 - numberOfAi0Value:
				k = max(k, p[0])
	print(-1 if k == math.inf else k)