You are given a sequence $A_1, A_2, \ldots, A_N$. You want all the elements of the sequence to be equal. In order to achieve that, you may perform zero or more moves. In each move, you must choose an index $i$ ($1 \le i \le N$), then choose $j = i-1$ or $j = i+1$ (it is not allowed to choose $j = 0$ or $j = N+1$) and change the value of $A_i$ to $A_j$ — in other words, you should replace the value of one element of the sequence by one of its adjacent elements.
What is the minimum number of moves you need to make in order to make all the elements of the sequence equal?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of moves.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $1 \le A_i \le 100$ for each valid $i$

-----Example Input-----
3
5
1 1 1 1 1
4
9 8 1 8
2
1 9

-----Example Output-----
0
2
1

-----Explanation-----
Example case 1: No moves are needed since all the elements are already equal.
Example case 3: We can perform one move on either $A_1$ or $A_2$.

Source: codechef | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms

Ad-hoc


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in list(set(l)):
		l1.append(l.count(i))
	print(len(l) - max(l1))


n = int(input())
for i in range(n):
	l = int(input())
	lis = list(map(int, input().split()))
	print(l - max([lis.count(lis[i]) for i in range(l)]))


for i in range(0, int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	a = 0
	for j in list1:
		b = list1.count(j)
		if b > a:
			a = b
	print(n - a)


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	C = 0
	for i in a:
		C = max(a.count(i), C)
	print(N - C)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = 0
	s = list(set(arr))
	for i in range(len(s)):
		m = max(m, arr.count(s[i]))
	print(n - m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	m = 0
	for i in s:
		m = max(m, a.count(i))
	print(n - m)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	se = set(li)
	max_count = 0
	for i in se:
		if li.count(i) > max_count:
			max_count = li.count(i)
	print(n - max_count)


for _ in range(int(input())):
	n = int(input())
	input_1 = list(map(int, input().split(' ')))
	dict_count = dict()
	for ele in input_1:
		if dict_count.get(ele) == None:
			dict_count[ele] = 1
		else:
			dict_count[ele] = dict_count[ele] + 1
	max_value = 0
	for (key, value) in dict_count.items():
		if max_value < value:
			max_value = value
	print(n - max_value)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	sum = 0
	for i in s:
		x = l.count(i)
		if x > sum:
			sum = x
	print(len(l) - sum)


def find(array):
	counter = 0
	number = array[0]
	for i in array:
		temp = array.count(i)
		if temp > counter:
			counter = temp
			number = i
			pass
		pass
	return number
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	most_repeated = find(arr)
	count = 0
	for i in arr:
		if i != most_repeated:
			count += 1
			pass
		pass
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = 0
	for i in range(n):
		c = 1
		for j in range(i + 1, n):
			if arr[i] == arr[j]:
				c += 1
		d = max(c, d)
	print(n - d)


for i in range(int(input())):
	n = int(input())
	t = input().split()
	m = set(t)
	ma = 0
	for j in m:
		x = t.count(j)
		if ma < x:
			ma = x
	print(n - ma)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for j in a:
		c = max(a.count(j), c)
	print(n - c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = set(l)
	a = []
	for i in k:
		a.append(l.count(i))
	m = max(a)
	print(n - m)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	c = 0
	d = 0
	e = 0
	ma = 0
	index = 0
	for i in range(len(a)):
		j = i + 1
		for k in range(j, len(a)):
			if a[i] == a[k]:
				c = c + 1
				break
	if c == len(a) - 1:
		print(0)
	else:
		for i in range(len(a)):
			j = i + 1
			f = 1
			for k in range(j, len(a)):
				if a[i] == a[k]:
					f = f + 1
			if f > ma:
				ma = f
				index = a[i]
		for i in [index]:
			for j in range(len(a)):
				if i != a[j]:
					d = d + 1
		if d > 0:
			print(d)
		else:
			for i in range(1, len(a)):
				if a[0] != a[i]:
					e = e + 1
			print(e)


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	max_count = 0
	for i in s:
		if a.count(i) > max_count:
			max_count = a.count(i)
	print(n - max_count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = Counter(list(map(int, input().split())))
	print(n - max(l.values()))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	for j in l:
		a = max(l.count(j), a)
	print(n - a)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	mc = 0
	for j in range(n):
		if a.count(a[j]) > mc:
			mc = a.count(a[j])
	print(n - mc)


from statistics import mode
a = []
for x in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	res = mode(a)
	c = 0
	for i in a:
		if i == res:
			c = c + 1
	print(n - c)


ans = []
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = 0
	s = set(arr)
	for i in s:
		if arr.count(i) > m:
			m = arr.count(i)
	ans.append(n - m)
for i in ans:
	print(i)


for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	u = set(a)
	max = 0
	for i in u:
		d = a.count(i)
		if max < d:
			max = d
	print(n - max)


t = int(input())
for i in range(t):
	n = int(input())
	l2 = list(map(int, input().split()))
	c = 0
	for j in l2:
		c = max(c, l2.count(j))
	print(n - c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dt = {}
	for i in l:
		dt[i] = dt.get(i, 0) + 1
	m = max(dt.values())
	print(n - m)


for i in range(int(input())):
	n = int(input())
	lst1 = list(map(int, input().split()))
	s = max(set(lst1), key=lst1.count)
	print(n - lst1.count(s))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 0
	for i in l:
		m = max(l.count(i), m)
	print(n - m)


n = int(input())
for i in range(n):
	m = int(input())
	c = 0
	lis = list(map(int, input().split()))
	for i in lis:
		c = max(lis.count(i), c)
		g = m - c
	print(g)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	B = set(A)
	L = []
	for j in range(len(B)):
		L.append(A.count(A[j]))
	print(len(A) - max(L))


from collections import Counter
T = int(input())
for i in range(T):
	n = int(input())
	lst = list(map(int, input().split()))
	count = Counter(lst)
	print(n - max(count.values()))


for i in range(int(input())):
	n1 = int(input())
	l = list(map(int, input().strip().split()))
	m = 0
	for i in l:
		m = max(l.count(i), m)
	print(n1 - m)


T = int(input())
for _ in range(T):
	n = int(input())
	number_list = list(map(int, input().split()))
	number_dict = {}
	for i in number_list:
		if i in number_dict:
			number_dict[i] += 1
		else:
			number_dict[i] = 1
	keymax = max(number_dict, key=lambda x: number_dict[x])
	print(n - number_dict[keymax])


for _ in range(int(input())):
	x = int(input())
	list1 = list(map(int, input().split()))
	ans = 0
	for i in range(x):
		if list1.count(list1[i]) > ans:
			ans = list1.count(list1[i])
	print(len(list1) - ans)


t = int(input())
for i in range(t):
	c = []
	n = int(input())
	a = list(map(int, input().split()))
	b = list(set(a))
	for i in b:
		k = a.count(i)
		c.append(k)
	if max(c) > 1:
		print(n - max(c))
	elif len(b) == 1 and max(c) == 1:
		print(n)
	else:
		print(n - 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(z) for z in input().split()]
	m = 0
	a1 = list(set(a))
	for i in range(len(a1)):
		if a.count(a1[i]) > m:
			m = a.count(a1[i])
	print(n - m)


for _ in range(int(input())):
	size = int(input())
	arr1 = [int(x) for x in input().split()]
	dict1 = {}
	if len([*set(arr1)]) == 1:
		print(0)
		continue
	for y in arr1:
		if y in dict1:
			dict1[y] += 1
		else:
			dict1[y] = 1
	print(size - max(dict1.values()))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = []
	for i in range(len(l)):
		r = l.count(l[i])
		k.append(r)
	s = max(k)
	print(len(l) - s)


for _ in range(int(input())):
	c = int(input())
	a = list(map(int, input().split()))
	b = 0
	for i in a:
		b = max(a.count(i), b)
	print(c - b)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	L = input().split()
	l = [eval(i) for i in L]
	k = Counter(l)
	c = k.values()
	print(n - max(c))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	max2 = 0
	for i in l:
		if l.count(i) > max2:
			max2 = l.count(i)
	print(n - max2)


for i in range(int(input())):
	n = int(input())
	A = [int(n) for n in input().split()]
	maxim = max(A, key=A.count)
	print(n - A.count(maxim))


for _ in range(int(input())):
	a = int(input())
	ass = list(map(int, input().split()))
	b = 0
	for i in range(a):
		if ass.count(ass[i]) > b:
			b = ass.count(ass[i])
	print(a - b)


def changeIt(n, arr):
	m = dict()
	for i in range(n):
		m[arr[i]] = m.get(arr[i], 0) + 1
	count = 0
	for i in m.keys():
		if m[i] > count:
			count = m[i]
		else:
			continue
	print(len(arr) - count)
	return
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	changeIt(n, arr)


from statistics import mode
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = mode(l)
	s = l.count(r)
	print(n - s)


for _ in range(int(input())):
	n = int(input())
	d = {}
	l = list(map(int, input().split()))
	for i in l:
		d[i] = l.count(i)
	x = 0
	for j in d:
		if d[j] > x:
			x = d[j]
	print(n - x)


from statistics import mode
t = int(input())
for i in range(t):
	b = int(input())
	l = list(map(int, input().split()))
	m = mode(l)
	c = l.count(m)
	print(b - c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in a:
		l.append(a.count(i))
	print(n - a.count(a[l.index(max(l))]))


for _ in range(int(input())):
	n = int(input())
	s1 = list(map(int, input().split()))
	l2 = []
	for i in s1:
		l2.append(s1.count(i))
	print(n - s1.count(s1[l2.index(max(l2))]))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	c = 0
	for i in s:
		if a.count(i) > c:
			c = a.count(i)
	print(n - c)


for i in range(int(input())):
	n = int(input())
	a = input().split()
	b = []
	for i in a:
		b.append(a.count(i))
	print(n - max(b))


from collections import Counter
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	c = dict(Counter(a))
	m = max(list(c.values()))
	print(n - m)


from collections import Counter
val = int(input())
for i in range(val):
	n = input()
	n = int(n)
	p = list(map(int, input().split()))
	c = Counter(p)
	print(n - max(c.values()))


tests = int(input())
for test in range(tests):
	n = int(input())
	a = [int(x) for x in input().split()]
	maxx = max(set(a), key=a.count)
	moves = a.index(maxx)
	if len(a) > 1:
		for i in range(moves + 1, len(a)):
			if a[i] != maxx:
				moves += 1
	print(moves)


def change_it(_list):
	if len(set(_list)) <= 2:
		return len(set(_list)) - 1
	k = []
	for i in range(len(_list)):
		r = _list.count(_list[i])
		k.append(r)
	s = max(k)
	return len(_list) - s

def __starting_point():
	t = int(input())
	for i in range(t):
		n = int(input())
		_list = list(map(int, input().split()))
		print(f'{change_it(_list)}')
__starting_point()


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	d = {}
	for i in list1:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	print(n - max(d.values()))


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = dict(Counter(l))
	m = max(list(x.values()))
	print(n - m)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	d = {}
	for i in lst:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	max = 0
	for i in d:
		if d[i] > max:
			max = d[i]
	print(n - max)


from statistics import mode
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	m = mode(l)
	for j in l:
		if j != m:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	c = 0
	for i in A:
		c = max(A.count(i), c)
	print(n - c)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().rstrip().split()]
	b = list(set(a))
	max1 = 0
	for i in range(0, len(b)):
		s = a.count(b[i])
		if s > max1:
			max1 = s
	print(n - max1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set(arr)
	maxi = 0
	for i in s:
		if arr.count(i) > maxi:
			maxi = arr.count(i)
	print(n - maxi)


from collections import Counter as c
for _ in range(int(input())):
	n = int(input())
	arra = list(map(int, input().split()))
	cc = c(arra)
	a = cc.most_common()[0][1]
	print(n - a)


for _ in range(int(input())):
	n = int(input())
	ass = list(map(int, input().split()))
	m = 0
	for i in range(n):
		if ass.count(ass[i]) > m:
			m = ass.count(ass[i])
	print(n - m)


from statistics import mode
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = mode(a)
	print(n - a.count(b))


from collections import Counter
t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	d = Counter(A)
	l = []
	for (i, j) in d.items():
		l.append(j)
	print(N - max(l))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	max1 = 0
	for i in A:
		if A.count(i) > max1:
			max1 = A.count(i)
	print(N - max1)


for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = set(l)
	v = []
	for i in l1:
		v.append(l.count(i))
	v1 = n - max(v)
	print(v1)


import statistics
t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	m = statistics.mode(d)
	s = n - d.count(m)
	print(s)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	se = set(m)
	max_count = 0
	for i in se:
		if m.count(i) > max_count:
			max_count = m.count(i)
	print(n - max_count)


n = int(input())
for i in range(n):
	n1 = int(input())
	l = list(map(int, input().split()))
	count = 0
	se = set(l)
	for i in se:
		if l.count(i) > count:
			count = l.count(i)
	print(n1 - count)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	c = l.count(l[0])
	for i in range(1, n):
		m = l.count(l[i])
		if m > c:
			c = m
	print(n - c)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max = 0
	for i in a:
		if a.count(i) > max:
			max = a.count(i)
	print(n - max)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	c = 1
	if len(l) == len(s):
		print(n - 1)
	else:
		s = list(s)
		for j in range(len(s)):
			if l.count(s[j]) > c:
				c = l.count(s[j])
		print(n - c)


n = int(input())
while n > 0:
	t = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	m = 1
	for v in d.values():
		if v > m:
			m = v
	print(t - m)
	n = n - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	b = set(a)
	ma = 0
	for j in b:
		p = a.count(j)
		if ma < p:
			ma = p
	print(n - ma)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	final = []
	x = sorted(l, key=l.count)
	for i in x:
		if i != x[-1]:
			final.append(i)
	print(len(final))


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	v = A[0]
	if A.count(v) == n:
		print(0)
		continue
	m = 0
	for i in A:
		o = A.count(i)
		if m < o:
			m = o
			k = i
	print(n - m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	count = 0
	for i in a:
		if a.count(i) > count:
			count = a.count(i)
	print(n - count)