You are given an array A of length N. 

You can perform the following operation on the array, as long as it has more than one element:
Choose any two adjacent elements, remove them from the array and insert their sum at that position.
Formally, if the current length of the array is |A|, you can choose an index 1 ≤ i < |A|, and transform the array into [A_{1}, A_{2}, \ldots, A_{i-1}, A_{i} + A_{i+1}, A_{i+2}, \ldots, A_{N}].

Note that after each operation, the length of array decreases by exactly 1.

Print the minimum number of operations to be applied on array A such that all the elements in the resulting array are equal. See sample explanation for more details.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line contains an integer N.
- The second line contains N space-separated integers, the elements of array A.

------ Output Format ------ 

For each test case, output on a new line the minimum number of operations required to make all the elements equal.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 3 \cdot 10^{4}$
$-3 \cdot 10^{4} ≤ A_{i} ≤ 3 \cdot 10^{4}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{4}$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
3
5 2 3
2
6 9
5
3 6 5 4 9
3
3 3 3

----- Sample Output 1 ------ 
1
1
2
0

----- explanation 1 ------ 
Test case $1$: It is optimal to remove $A_{2}$ and $A_{3}$ in the first operation, after which the array becomes $[5,5]$ — all of whose elements are equal.

Test case $2$: Remove $A_{1}$ and $A_{2}$ after which the array becomes $[15]$, which contains equal elements because it is of length $1$.

Test case $3$: First remove $A_{3}$ and $A_{4}$ after which the updated array $A$ becomes $[3,6,9,9]$. Now remove $A_{1}$ and $A_{2}$ after which the array becomes $[9,9,9]$. 

Test case $4$: The array elements are already equal.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
t = int(input())
for y in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	adj = []
	main_count = float('-inf')
	main_number = float('inf')
	big_fail = float('-inf')
	adj.append(arr[0])
	i = 0
	for x in arr[1:]:
		i = i + 1
		adj.append(adj[i - 1] + arr[i])
	i = -1
	l = len(adj)
	if adj[-1] == 0:
		z = adj.count(0)
		if z > main_count:
			main_count = z
	else:
		for x in adj:
			i += 1
			if x != 0 and (abs(x) > big_fail or len(adj) < 10000):
				if adj[-1] % x == 0 and adj[-1] / x > 0 and (abs(x) < main_number) and (abs(adj[-1]) // abs(x) <= l - i):
					num = x
					count = 1
					for y in adj[i + 1:]:
						if y - num == x:
							count += 1
							num = y
							if num == adj[-1]:
								break
					if num == adj[-1]:
						if count > main_count:
							main_count = count
							main_number = abs(x)
					else:
						big_fail = abs(x)
	print(len(arr) - main_count)


import math

def minimum_move(n, array):
	prefix_sum = [array[0]]
	for i in range(1, len(array)):
		prefix_sum.append(prefix_sum[i - 1] + array[i])
	total = prefix_sum[-1]
	if total == 0:
		ans = n
		for num in prefix_sum:
			if num == 0:
				ans -= 1
		return ans
	sign = 1 if total > 0 else -1
	total = abs(total)

	def possible(l, e):
		s = 0
		for num in prefix_sum:
			if num == (s + 1) * e:
				s += 1
		return s >= l
	ans = n - 1
	for i in reversed(range(1, math.ceil(math.sqrt(total)) + 1)):
		if total % i != 0:
			continue
		if possible(i, total // i * sign):
			ans = min(ans, n - i)
		if possible(total // i, i * sign):
			ans = min(ans, n - total // i)
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	array = list(map(int, input().split(' ')))
	print(minimum_move(N, array))


import sys
import itertools
MAXN = 30000
SQRTMAXN = 175
ISPRIME = [1] * (MAXN + 1)
PRIMES = [2]

def sieve():
	for i in range(MAXN // 2):
		ISPRIME[2 * i] = 0
	ISPRIME[1] = 0
	ISPRIME[2] = 1
	for i in range(3, SQRTMAXN):
		if ISPRIME[i]:
			for j in range(i * i, MAXN + 1, 2 * i):
				ISPRIME[j] = 0
	for i in range(3, MAXN + 1, 2):
		if ISPRIME[i]:
			PRIMES.append(i)
sieve()

def decomp(N):
	ANS = {}
	if N < 2:
		return {}
	for P in PRIMES:
		while N % P == 0:
			ANS[P] = ANS.get(P, 0) + 1
			N //= P
		if N == 1:
			break
	if N > 1:
		ANS[N] = 1
	return ANS

def divisors(N):
	if N == 0:
		return set()
	D = set()
	dec = decomp(N)
	for xxx in itertools.product(*(range(x + 1) for x in dec.values())):
		M = 1
		for (p, powa) in zip(dec.keys(), xxx):
			M *= p ** powa
		D.add(M)
	return D

def issubsequence(subseq, arr):
	a = 0
	for s in range(len(subseq)):
		try:
			a = arr.index(subseq[s], a) + 1
		except:
			return False
	return True

def main(N, A):
	cumS = [0] * N
	for i in range(N):
		cumS[i] = cumS[i - 1] + A[i]
	if cumS[N - 1] == 0:
		return N - cumS.count(0)
	if cumS[N - 1] != 0:
		divi = sorted([d for d in divisors(abs(cumS[N - 1])) if d <= N], reverse=True)
	else:
		divi = sorted([d for d in range(1, N + 1)], reverse=True)
	for d in divi:
		subseq = [cumS[N - 1] // d * k for k in range(1, d + 1)]
		if issubsequence(subseq, cumS):
			return N - d
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()[:N]]
	print(main(N, A))


def partitions2(array, n, K):
	if e % K != 0:
		return False
	temp = 0
	count = n - K
	c = False
	imp = True
	cursum = 0
	for i in range(n):
		if count < 0:
			imp = False
			break
		if cursum + array[i] == e / K and temp <= K:
			temp += 1
			c = False
			cursum = 0
		elif cursum + array[i] == -e / K and temp > K:
			temp = temp - 1
			c = False
			cursum = 0
		else:
			cursum += array[i]
		if c:
			count = count - 1
		c = True
	if count < 0:
		imp = False
	return temp == K and imp
x = int(input())
for i in range(x):
	N = int(input())
	l = list(map(int, input().split()))
	e = sum(l)
	for i in range(N, 0, -1):
		k = i
		if partitions2(l, N, k):
			val = k
			break
	print(N - val)


def cal(x, ps):
	n = len(ps)
	mul = 0
	i = 0
	while i < n and mul // x < ps[-1] // x:
		if mul + x == ps[i]:
			mul += x
		i += 1
	cnt = ps[-1] // x if mul == ps[-1] else 1
	return n - cnt
for t in range(int(input().strip())):
	n = int(input().strip())
	a = tuple(map(int, input().strip().split()))
	ps = [a[0]]
	for i in range(1, n):
		ps.append(ps[i - 1] + a[i])
	cnt0 = ps.count(0)
	ans = n - (cnt0 if ps[-1] == 0 else 1)
	f = 1
	while f * f <= abs(ps[-1]):
		if abs(ps[-1]) % f == 0:
			ans = min(ans, cal(f * ps[-1] // abs(ps[-1]), ps), cal(ps[-1] // f, ps))
		f += 1
	print(ans)


def poss(res, elem, len):
	cnt = 0
	for i in res:
		if i == elem * (cnt + 1):
			cnt += 1
	return cnt >= len
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	res = [sum(ar[:i + 1]) for i in range(len(ar))]
	s = res[-1]
	ans = 0
	if s == 0:
		cn = res.count(0)
		ans = n - cn
	else:
		sn = 1 if s > 0 else -1
		s = abs(s)
		ans = n - 1
		i = 1
		while i * i <= s:
			if s % i != 0:
				i += 1
				continue
			ln1 = i
			elem1 = s // i * sn
			ln2 = s // i
			elem2 = i * sn
			i += 1
			if poss(res, elem1, ln1):
				ans = min(ans, n - ln1)
			if poss(res, elem2, ln2):
				ans = min(ans, n - ln2)
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	p = [0] * n
	p[0] = a[0]
	for i in range(1, n):
		p[i] = a[i] + p[i - 1]
	f = []
	pos = 1
	if s < 0:
		pos = -1
	for i in range(1, int(math.sqrt(abs(s))) + 1):
		if s % i == 0:
			f.append(pos * i)
			if i != abs(s // i):
				f.append(s // i)
	ans = n - 1
	if s == 0:
		z = p.count(0)
		ans = min(ans, n - z)
	else:
		for i in range(len(f)):
			count = 1
			for j in range(n):
				if p[j] == f[i] * count:
					count = count + 1
			if abs((count - 1) * f[i]) >= abs(s):
				ans = min(ans, n - s // f[i])
	print(ans)


t = int(float(input()))
for _ in range(t):
	n = int(float(input()))
	a = list(map(int, input().split()))
	s = sum(a)
	prefix_sum = a[:]
	for i in range(1, n):
		prefix_sum[i] += prefix_sum[i - 1]
	if s == 0:
		c = 0
		for i in range(n):
			if prefix_sum[i] != 0:
				c += 1
		print(c)
	else:
		for i in range(n, 0, -1):
			if s % i == 0:
				f = s // i
				x = f
				for j in range(n):
					if prefix_sum[j] == x:
						x += f
					if x - f == s:
						break
				if x - f == s:
					print(n - i)
					break


from sys import stdin
from itertools import accumulate
from bisect import bisect

def makeLPF(f_limit):
	lpf = [2, 1] * (f_limit // 2 + 1)
	if f_limit % 2 == 0:
		lpf.pop()
	lpf[0:3] = [0, 0, 1]
	k = 3
	while k * k <= f_limit:
		if lpf[k] == 1:
			for m in range(k * k, f_limit + 1, 2 * k):
				if lpf[m] == 1:
					lpf[m] = k
		k += 2
	return lpf

def factors(num, primes, lim):
	red = abs(num)
	fac = [1]
	if red < 2:
		return [1]
	for p in primes[:bisect(primes, lim)]:
		if red % p == 0:
			nfac = [1]
			while red % p == 0:
				red //= p
				nfac.append(nfac[-1] * p)
			fac = [f * n for n in nfac for f in fac]
		if p > red:
			break
	if red > 1 and red <= lim:
		fac.extend([red * f for f in fac])
	return sorted(fac)
LPF = makeLPF(30000)
prs = [v for (v, lp) in enumerate(LPF) if lp == 1]
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	S = list(map(int, inp().split()))
	acS = list(accumulate(S))
	tot = acS[-1]
	if tot == 0:
		print(N - acS.count(0))
		continue
	atot = abs(tot)
	fails = []
	best = 1
	fac = factors(tot, prs, N)
	if fac[-1] > N:
		fac = fac[:bisect(fac, N)]
	for partn in fac[1:]:
		for f in fails:
			if partn % f == 0:
				break
		else:
			inc = tot // partn
			ix = 0
			for v in range(inc, tot, inc):
				try:
					ix = acS.index(v, ix)
				except ValueError:
					fails.append(partn)
					break
			else:
				best = partn
	print(N - best)


from sys import stdin
from itertools import accumulate
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	accA = list(accumulate(map(int, inp().split())))
	tot = accA[-1]
	if tot == 0:
		print(N - accA.count(0))
		continue
	atot = abs(tot)
	partn = min(N, atot)
	fails = []
	best = 1
	for partn in range(2, min(N, atot) + 1):
		if tot % partn == 0:
			for f in fails:
				if partn % f == 0:
					break
			else:
				inc = tot // partn
				ix = 0
				for v in range(inc, tot, inc):
					try:
						ix = accA.index(v, ix)
					except ValueError:
						fails.append(partn)
						break
				else:
					best = partn
	print(N - best)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	s = 0
	for i in range(n):
		s += a[i]
		b.append(s)
	if s == 0:
		c = 0
		for i in range(n):
			if b[i] != 0:
				c += 1
		print(c)
	else:
		for i in range(n, 0, -1):
			if s % i == 0:
				d = s // i
				e = d
				for j in range(n):
					if b[j] == e:
						e += d
					if e - d == s:
						break
				if e - d == s:
					print(n - i)
					break


def func(n, arr):
	total = sum(arr)
	if total == 0:
		a = [arr[0]]
		for i in range(1, n):
			a.append(a[i - 1] + arr[i])
		i = a.index(total)
		moves = i
		curr = i
		for j in range(i + 1, n):
			if a[j] == total:
				moves += j - curr - 1
				curr = j
		return moves
	curr = 0
	d = {}
	for i in range(n):
		curr += arr[i]
		if d.get(curr) == None:
			d[curr] = [i]
		else:
			d[curr].append(i)
	for i in range(n, 0, -1):
		if total % i == 0:
			num = total // i
			curr = total
			index = n
			while curr != 0:
				if d.get(curr) != None:
					found = False
					for j in range(len(d[curr]) - 1, -1, -1):
						if d[curr][j] < index:
							index = d[curr][j]
							found = True
							break
					if not found:
						break
					curr -= num
				else:
					break
			if curr == 0:
				return n - i
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(func(n, arr))


from sys import stdin
from itertools import accumulate
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(inp())
	S = list(map(int, inp().split()))
	acS = list(accumulate(S))
	tot = acS[-1]
	if tot == 0:
		print(N - acS.count(0))
		continue
	atot = abs(tot)
	partn = min(N, atot)
	while partn > 1:
		if tot % partn == 0:
			inc = tot // partn
			ix = 0
			for v in range(inc, tot, inc):
				try:
					ix = acS.index(v, ix)
				except ValueError:
					break
			else:
				break
		partn = atot // (1 + atot // partn)
	print(N - partn)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	SUM = sum(A)
	op = -1
	for i in range(n, 0, -1):
		if SUM % i == 0:
			if SUM != 0:
				target = SUM // i
				SS = SUM
				j = 0
				sd = 0
				flag = 0
				while j < n:
					if sd + A[j] == target:
						SS = SS - (sd + A[j])
						flag += 1
						sd = 0
						if SS == 0:
							break
					else:
						sd += A[j]
					j += 1
				if flag * target == SUM:
					op = n - flag
					break
			else:
				target = SUM // i
				j = 0
				sd = 0
				flag = 0
				while j < n:
					sd += A[j]
					if sd == target:
						flag += 1
						sd = 0
					j += 1
				if flag * target == SUM:
					op = n - flag
					break
	if op != -1:
		print(op)


from math import floor

def split_possible(n, arr, n1):
	ss_sum = sum(arr) // n1
	(ss, ss_len) = ([], 0)
	curr = 0
	for i in range(n):
		curr += arr[i]
		if curr == ss_sum and ss_len < n1:
			ss.append(curr)
			curr = 0
			ss_len += 1
	if sum(ss) != ss_sum * n1 or curr != 0:
		return False
	return True

def zero_possible(n, arr):
	(ss, ss_len) = ([], 0)
	curr = 'NA'
	for i in range(n):
		curr = curr + arr[i] if curr != 'NA' else arr[i]
		if curr == 0:
			ss.append(curr)
			curr = 'NA' if i != n - 1 else 'FIN'
			ss_len += 1
	if curr == 'FIN':
		return (True, ss_len)
	return (False, -1)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = abs(sum(arr))
	if arr == [arr[0]] * n:
		print(0)
	elif n == 2:
		print(1)
	else:
		k = 1
		lim = floor(s ** 0.5) + 1
		if s != 0:
			for el in range(1, min(lim, n) + 1):
				if s % el == 0:
					if split_possible(n, arr, el):
						k = max(k, el)
					if s // el <= n and split_possible(n, arr, s // el):
						k = max(k, s // el)
		if s == 0:
			(f, v) = zero_possible(n, arr)
			if f:
				k = max(k, v)
		print(n - k)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	d_len = 0
	s = sum(l)
	for i in range(1, int(math.sqrt(abs(s))) + 1):
		if s % i == 0:
			if s < 0:
				r = -1
			else:
				r = 1
			if abs(s) // i <= n:
				d[r * i] = abs(s // i)
				d_len += 1
			if abs(i) <= n and i != s // i:
				d[s // i] = abs(i)
				d_len += 1
	if s > 0:
		d = {k: v for (k, v) in sorted(d.items(), key=lambda x: x[0])}
	else:
		d = {k: v for (k, v) in sorted(d.items(), reverse=True, key=lambda x: x[0])}
	if d == {}:
		count = 0
		for i in range(n - 1):
			if l[i] != 0:
				l[i + 1] = l[i] + l[i + 1]
				count += 1
		if l[-1] != 0:
			count += 1
		print(count)
	elif d_len == 1:
		(a, b) = d.popitem()
		print(n - b)
	else:
		flag = False
		for (i, j) in d.items():
			k = l[:]
			count = 0
			for x in range(n - 1):
				if k[x] != i:
					k[x + 1] = k[x] + k[x + 1]
					count += 1
			if k[-1] != i:
				count += 1
			if count <= n - j:
				print(n - j)
				flag = True
				break


NEG = -10 ** 9 - 7

def factors(n):
	neg = False
	if n < 0:
		neg = True
		n = abs(n)
	ret = set()
	if n == 0:
		ret.add(0)
		return ret
	for i in range(1, n, 1):
		if i * i > n:
			break
		if n % i == 0:
			ret.add(i)
			ret.add(int(n / i))
	if neg:
		nret = set()
		for i in ret:
			nret.add(0 - i)
		return nret
	return ret

def checkComb(a, sm):
	ts = NEG
	sec = 0
	for i in range(len(a)):
		if ts == NEG:
			ts = 0
		ts += a[i]
		if ts == sm:
			sec += 1
			ts = NEG
	if ts == NEG or ts == 0:
		return len(a) - sec
	if ts % abs(sm) == 0:
		mul = int(abs(ts) / abs(sm))
		if sm * mul == ts:
			return -1
		return len(a) - (sec - mul)
	return -1
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	sm = sum(a)
	ans = len(a) - 1
	if len(a) <= 1:
		print('0')
		continue
	fac = factors(sm)
	for f in fac:
		st = checkComb(a, f)
		if st >= 0 and st < ans:
			ans = st
	print(int(ans))


from typing import List

def contains(l1: List[int], l2: List[int]) -> bool:
	(i, j) = (0, 0)
	while i < len(l1) and j < len(l2):
		if l1[i] == l2[j]:
			i += 1
			j += 1
		else:
			j += 1
	return i == len(l1)

def solve(t):
	N = int(input())
	A = list(map(int, input().split()))
	answer = N - 1
	total = sum(A)
	prefix_sum_A = [a for a in A]
	for i in range(1, N):
		prefix_sum_A[i] += prefix_sum_A[i - 1]
	for target_length in reversed(range(2, N + 1)):
		if total % target_length == 0:
			target_value = total // target_length
			prefix_sums = [i * target_value for i in range(1, target_length + 1)]
			if contains(prefix_sums, prefix_sum_A):
				answer = N - target_length
				break
	print(answer)
T = int(input())
for t in range(T):
	solve(t + 1)


from itertools import accumulate

def check_valid(acc, ind, i):
	res = ind
	ind += 1
	mult = 2
	sm = acc[-1]
	try:
		while ind < len(acc) and abs(i * mult) <= abs(sm):
			ind2 = acc.index(i * mult, ind)
			res += ind2 - ind
			mult += 1
			ind = ind2 + 1
		res += len(acc) - ind
		return res
	except ValueError:
		return -1
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	acc = list(accumulate(li))
	acc_set = set(acc)
	sm = acc[-1]
	ans = []
	if sm != 0:
		for (ind, i) in enumerate(acc):
			if i != 0 and sm % i == 0 and (sm * i > 0) and (set(range(i, sm + 1, i)) - acc_set == set()):
				res = check_valid(acc, ind, i)
				if res != -1:
					ans.append(res)
		print(min(ans))
	else:
		ind = acc.index(0)
		res = check_valid(acc, ind, 0)
		print(res)


from math import sqrt
from sys import stdin
input = stdin.readline

def factors(n):
	f = set()
	step = 2 if n % 2 == 1 else 1
	for x in range(1, int(sqrt(n)) + 1, step):
		(q, r) = divmod(n, x)
		if r == 0:
			f.add(x)
			f.add(q)
	return f

def solve(N, A):
	total = sum(A)
	if total == 0:
		count = 0
		subtotal = 0
		for a in A:
			if subtotal + a != 0:
				subtotal += a
				count += 1
			else:
				subtotal = 0
		assert subtotal == 0
		return count
	else:
		sign = 1 if total >= 0 else -1
		total = abs(total)
		divs = factors(total)
		minimum = N - 1
		for d in divs:
			if total // d <= N:
				count = 0
				subtotal = 0
				number = 0
				for a in A:
					if subtotal + a != sign * d or number == total // d:
						subtotal += a
						count += 1
					else:
						subtotal = 0
						number += 1
				if subtotal == 0:
					minimum = min(minimum, count)
					assert number == total // d
		return minimum
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(solve(N, A))


import sys
input = sys.stdin.readline

def check(part_sum, k, A):
	curr_sum = None
	for (i, a) in enumerate(A):
		curr_sum = (0 if curr_sum is None else curr_sum) + a
		if k > 1 and curr_sum == part_sum:
			curr_sum = None
			k -= 1
	return k == 1 and curr_sum == part_sum
for _ in range(int(input().strip())):
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	prefix = [0] * (N + 1)
	for (i, a) in enumerate(A):
		prefix[i + 1] = a + prefix[i]
	total = prefix[-1]
	for k in reversed(range(1, N + 1)):
		if total % k != 0:
			continue
		part_sum = total // k
		if check(part_sum, k, A):
			print(N - k)
			break