To help those contestants who struggle a lot in contests, the headquarters of Codeforces are planning to introduce Division 5. In this new division, the tags of all problems will be announced prior to the round to help the contestants.

The contest consists of $n$ problems, where the tag of the $i$-th problem is denoted by an integer $a_i$.

You want to AK (solve all problems). To do that, you must solve the problems in some order. To make the contest funnier, you created extra limitations on yourself. You do not want to solve two problems consecutively with the same tag since it is boring. Also, you are afraid of big jumps in difficulties while solving them, so you want to minimize the number of times that you solve two problems consecutively that are not adjacent in the contest order.

Formally, your solve order can be described by a permutation $p$ of length $n$. The cost of a permutation is defined as the number of indices $i$ ($1\le i<n$) where $|p_{i+1}-p_i|>1$. You have the requirement that $a_{p_i}\ne a_{p_{i+1}}$ for all $1\le i< n$.

You want to know the minimum possible cost of permutation that satisfies the requirement. If no permutations meet this requirement, you should report about it.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of problems in the contest.

The next line contains $n$ integers $a_1,a_2,\ldots a_n$ ($1 \le a_i \le n$) — the tags of the problems.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, if there are no permutations that satisfy the required condition, print $-1$. Otherwise, print the minimum possible cost of a permutation that satisfies the required condition.


-----Examples-----

Input
4
6
2 1 2 3 1 1
5
1 1 1 2 2
8
7 7 2 7 7 1 8 7
10
1 2 3 4 1 1 2 3 4 1
Output
1
3
-1
2


-----Note-----

In the first test case, let $p=[5, 4, 3, 2, 1, 6]$. The cost is $1$ because we jump from $p_5=1$ to $p_6=6$, and $|6-1|>1$. This permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $1$.

In the second test case, let $p=[1,5,2,4,3]$. The cost is $3$ because $|p_2-p_1|>1$, $|p_3-p_2|>1$, and $|p_4-p_3|>1$. The permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $3$.

In the third test case, for any order of solving the problems, we will solve two problems with the same tag consecutively, so the answer is $-1$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
def calc(A):
	N = len(A)
	if N == 1:
		return 0
	X = [0] * N
	for a in A:
		X[a] += 1
	if max(X) > (N + 1) // 2:
		return -1
	Y = [0] * N
	Y[A[0]] += 1
	Y[A[-1]] += 1
	for (a, b) in zip(A, A[1:]):
		if a == b:
			Y[a] += 2
	(su, ma) = (sum(Y), max(Y))
	cc = su - ma
	return su // 2 - 1 + max(ma - cc - 2, 0) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	print(calc(A))


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		cnt = 0
		aCnt = [0] * n
		for i in range(n):
			aCnt[a[i] - 1] += 1
		flag = True
		for elem in aCnt:
			if elem > n - n // 2:
				flag = False
		if not flag:
			print(-1)
			continue
		endCountDouble = [0] * (n + 1)
		endCountSingle = [0] * (n + 1)
		last = a[0]
		lastInd = 0
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				cnt += 1
				if last == a[i]:
					endCountDouble[last] += 1
				else:
					endCountSingle[last] += 1
					endCountSingle[a[i]] += 1
					last = a[i]
				lastInd = i
		if last == a[n - 1]:
			endCountDouble[last] += 1
		else:
			endCountSingle[last] += 1
			endCountSingle[a[n - 1]] += 1
			last = a[n - 1]
		segCount = cnt + 1
		adjCount = 0
		whattoAdj = 0
		for i in range(n + 1):
			if endCountDouble[i] > segCount - endCountSingle[i] - (segCount - endCountSingle[i]) // 2:
				adjCount = endCountDouble[i] - (segCount - endCountSingle[i] - (segCount - endCountSingle[i]) // 2)
				whattoAdj = i
		if adjCount != 0:
			badPair = endCountDouble[whattoAdj]
			goodPair = segCount - endCountSingle[whattoAdj] - endCountDouble[whattoAdj]
			adjAble = 0
			for i in range(n - 1):
				if a[i] != i and a[i + 1] != i:
					adjAble += 1
			if adjAble >= badPair - goodPair - 1:
				print(cnt + badPair - goodPair - 1)
			else:
				print(-1)
		else:
			print(cnt)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	Counts = [0] * (N + 1)
	for a in A:
		Counts[a] += 1
	ma = max(Counts)
	if ma * 2 - 1 > N:
		print(-1)
		continue
	Cons = [0] * (N + 1)
	for (a1, a2) in zip(A, A[1:]):
		if a1 == a2:
			Cons[a1] += 1
	ans1 = sum(Cons)
	ma = -1
	ama = -101010101
	for (i, cons) in enumerate(Cons):
		if ma < cons:
			ama = i
			ma = cons
	a_old = A[0]
	left = A[0]
	C = [0, 0, 0]
	for a in A[1:] + [A[-1]]:
		if a == a_old:
			right = a
			C[(left == ama) + (right == ama)] += 1
			left = a
		a_old = a
	C[2] -= C[0]
	if C[2] <= 1:
		ans = ans1
	else:
		ans = ans1 + C[2] - 1
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()

def calc(A):
	N = len(A)
	if N == 1:
		return 0
	X = [0] * N
	for a in A:
		X[a] += 1
	if max(X) > (N + 1) // 2:
		return -1
	Y = [0] * N
	Y[A[0]] += 1
	Y[A[-1]] += 1
	for (a, b) in zip(A, A[1:]):
		if a == b:
			Y[a] += 2
	(su, ma) = (sum(Y), max(Y))
	cc = su - ma
	return su // 2 - 1 + max(ma - cc - 2, 0) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	print(calc(A))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	N = n
	a = list(map(int, input().split()))
	a = [a[i] - 1 for i in range(n)]
	E = []
	cnt = [0 for i in range(n)]
	L = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			cnt[a[i - 1]] += 1
			cnt[a[L]] += 1
			E.append((L, i - 1))
			L = i
	cnt[a[n - 1]] += 1
	cnt[a[L]] += 1
	E.append((L, n - 1))
	idx = -1
	M = max(cnt)
	for i in range(n):
		if cnt[i] == M:
			idx = i
			break
	k = len(E)
	cut = 0
	for (L, R) in E:
		for i in range(L, R):
			if a[i] != idx and a[i + 1] != idx:
				cut += 1
	ans = -1
	if k + 1 >= M:
		ans = k - 1
	else:
		need = M - (k + 1)
		if need <= cut:
			ans = M - 2
	print(ans)


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	alst = list(map(int, input().split()))
	cnt = [0 for _ in range(n + 1)]
	for a in alst:
		cnt[a] += 1
	if max(cnt) > (n + 1) / 2:
		print(-1)
		return
	ans = 0
	end = [0 for _ in range(n + 1)]
	for i in range(n - 1):
		if alst[i] == alst[i + 1]:
			end[alst[i]] += 1
			end[alst[i + 1]] += 1
			ans += 1
	end[alst[0]] += 1
	end[alst[-1]] += 1
	print(ans + max(0, max(end) - ans - 2))
for _ in range(int(input())):
	main()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	if max(Counter(A).values()) > (n + 1) // 2:
		print(-1)
	else:
		k = 0
		cnt = Counter()
		cnt[A[0]] += 1
		cnt[A[-1]] += 1
		for i in range(n - 1):
			if A[i] == A[i + 1]:
				cnt[A[i]] += 2
				k += 1
		print(k + max(0, max(cnt.values()) - (k + 2)))


(T,) = map(int, input().split())
for _ in range(T):
	(N,) = map(int, input().split())
	X = list(map(int, input().split()))
	d = [0] * (N + 1)
	for x in X:
		d[x] += 1
	if max(d) > (N + 1) // 2:
		print(-1)
		continue
	L = []
	stack = []
	for i in range(N):
		if len(stack) == 0 or stack[-1] != X[i]:
			stack.append(X[i])
		else:
			L.append(stack)
			stack = [X[i]]
	if stack:
		L.append(stack)
	cnt = [0] * (N + 1)
	for st in L:
		if st[0] == st[-1]:
			cnt[st[0]] += 1
	(mx, mxi) = (0, 0)
	for i in range(N + 1):
		if cnt[i] > mx:
			(mx, mxi) = (cnt[i], i)
	tmp = 0
	for st in L:
		if st[0] != mxi and st[-1] != mxi:
			tmp += 1
	print(len(L) - 1 + max(0, mx - tmp - 1))


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	n = int(input())
	l = input().split()
	li = [int(i) for i in l]
	hashi = dict()
	for i in li:
		if i in hashi:
			hashi[i] += 1
		else:
			hashi[i] = 1
	poss = 1
	for i in hashi:
		if hashi[i] > (n + 1) // 2:
			poss = 0
			break
	if poss == 0:
		print(-1)
		continue
	hashi = dict()
	ok = 0
	for i in range(n - 1):
		if li[i + 1] == li[i]:
			ok += 1
			if li[i] not in hashi:
				hashi[li[i]] = 0
			hashi[li[i]] += 1
			hashi[li[i + 1]] += 1
	if li[0] not in hashi:
		hashi[li[0]] = 0
	if li[-1] not in hashi:
		hashi[li[-1]] = 0
	hashi[li[0]] += 1
	hashi[li[-1]] += 1
	maxa = 0
	for i in hashi:
		maxa = max(maxa, ok + max(0, hashi[i] - ok - 2))
	print(maxa)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * (n + 1)
	for e in a:
		c[e] += 1
	if max(c) >= (n + 1) // 2 + 1:
		print(-1)
		continue
	count = 1
	s = 0
	c = [0] * (n + 1)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			count += 1
			c[a[s]] += 1
			c[a[i]] += 1
			s = i + 1
	c[a[s]] += 1
	c[a[n - 1]] += 1
	mx = max(c)
	ss = sum(c)
	if mx - 2 <= ss - mx:
		print(count - 1)
	else:
		count += (mx - 2 - (ss - mx)) // 2
		print(count - 1)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	C = [0] * (n + 1)
	for a in A:
		C[a] += 1
	MAX = -1
	MAXI = -1
	for i in range(n + 1):
		if C[i] > MAX:
			MAX = C[i]
			MAXI = i
	if MAX > (n + 1) // 2:
		print(-1)
		continue
	NOW = A[0]
	T = []
	for i in range(n - 1):
		if A[i] == A[i + 1]:
			T.append((NOW, A[i]))
			NOW = A[i + 1]
	T.append((NOW, A[-1]))
	D = [0] * (n + 1)
	OTHER = [0] * (n + 1)
	for (x, y) in T:
		if x == y:
			D[x] += 1
			OTHER[x] += 1
		else:
			OTHER[x] += 1
			OTHER[y] += 1
	TUIKA = 0
	LEN = len(T)
	for i in range(n + 1):
		if D[i] > LEN - OTHER[i] + 1:
			TUIKA += D[i] - (LEN - OTHER[i] + 1)
	print(LEN - 1 + TUIKA)


import sys, io, os
Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
o = []
for _ in range(int(Z())):
	n = int(Z())
	a = [*map(int, Z().split())]
	cn = p = a[0]
	pn = d = 0
	e = [0] * n
	b = [0] * n
	c = [0] * n
	for i in range(n):
		if a[i] == p:
			if pn:
				if pn != p:
					b[pn - 1] += 1
				else:
					e[p - 1] += 1
				b[p - 1] += 1
				d += 1
			pn = p
		p = a[i]
		c[p - 1] += 1
	if pn != p:
		b[pn - 1] += 1
	else:
		e[p - 1] += 1
	b[p - 1] += 1
	if 2 * max(c) - 1 > n:
		o.append('-1')
		continue
	m = 0
	s = sum(b)
	for i in range(n):
		dl = max(0, e[i] - 2 - d + b[i])
		m = max(dl, m)
	o.append(str(d + m))
print('\n'.join(o))