Chef just got a box of chocolates as his birthday gift. The box contains $N$ chocolates in a row (numbered $1$ through $N$), where $N$ is even. For each valid $i$, the $i$-th chocolate has a sweetness value $W_i$.
Chef wants to eat all the chocolates in the first half of the box and leave all chocolates in the second half uneaten. Since he does not like chocolates that are too sweet, he will be unhappy if at least one of the chocolates he eats has the maximum sweetness among all the chocolates in the box.
A right cyclic shift by $k$ chocolates ($0 \le k < N$) consists of moving the last $k$ chocolates in the row to the beginning in the same order and moving each of the remaining $N-k$ chocolates $k$ places to the right. Before eating the first half of the chocolates, Chef wants to perform some right cyclic shift in such a way that he will not be unhappy after eating them. Find the number of ways to do this, i.e. the number of valid integers $k$ such that if Chef performs the right cyclic shift by $k$ chocolates and then eats the first half of the chocolates in the box, he does not become unhappy.

-----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 $W_1, W_2, \ldots, W_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of shifts for which Chef does not become unhappy.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le N \le 10^5$
- $N$ is even
- $1 \le W_i \le 10^5$ for each valid $i$

-----Example Input-----
2
6
1 1 2 1 1 1
6
1 1 2 1 1 2

-----Example Output-----
3
0

-----Explanation-----
Example case 1: The three valid right shifts and the contents of the box for these shifts are:
- shift by $k = 1$: $(1, 1, 1, 2, 1, 1)$
- shift by $k = 2$: $(1, 1, 1, 1, 2, 1)$
- shift by $k = 3$: $(1, 1, 1, 1, 1, 2)$

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	a = int(input())
	cho = list(map(int, input().split()))
	maxc = max(cho)
	start = cho.index(maxc)
	mid = int(len(cho) / 2)
	for j in range(len(cho) - 1, 0, -1):
		if cho[j] == maxc:
			end = j
			break
	ans = len(cho) - end - (mid - start)
	print(max(0, ans))


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	m = max(s)
	c = []
	for i in range(n):
		if s[i] == m:
			c.append(i)
	if len(c) == 1:
		print(n // 2)
	elif c[-1] - c[0] + 1 > n // 2:
		print(0)
	else:
		x = c[-1] - c[0]
		print(n // 2 - x)


for i in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	m = max(w)
	x = w.index(m)
	k = w[::-1].index(m)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


for _ in range(int(input())):
	n = int(input())
	w = (*map(int, input().split()),)
	m = 0
	for i in range(n):
		if w[i] > w[m]:
			m = i
	count = 0
	gap = 0
	for i in range(m + 1, m + n + 1):
		if w[i % n] == w[m]:
			count += max(0, gap - n // 2 + 1)
			gap = 0
		else:
			gap += 1
	print(count)


try:
	T = int(input())
	while T > 0:
		N = int(input())
		midway = N // 2 - 1
		num = list(map(int, input().split()[:N]))
		max_beg = max(num)
		first_occr = num.index(max_beg)
		num.reverse()
		last_occr = num.index(max_beg)
		last_occr = N - 1 - last_occr
		if last_occr - first_occr >= midway:
			print(0)
		elif first_occr == last_occr:
			first_occr = midway
			print(N - 1 - first_occr)
		else:
			gap = last_occr - first_occr
			first_occr = midway
			last_occr = first_occr + gap
			print(N - 1 - last_occr)
		T -= 1
except EOFError as e:
	print('')


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	x = l1.index(max(l1))
	y = n - l1[::-1].index(max(l1)) - 1
	if y - x > n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a)
	x = a.index(b)
	k = a[::-1].index(b)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	i1 = l.index(m)
	i2 = n - l[::-1].index(m) - 1
	if abs(i1 - i2) < n // 2:
		print(n // 2 - (i2 - i1))
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	boxes = list(map(int, input().split()))
	res = max(boxes)
	dic = []
	for i in range(n):
		if boxes[i] == res:
			dic.append(i + 1)
	dic.append(dic[0] + n)
	a = n // 2
	ans = 0
	for i in range(1, len(dic)):
		ans += max(0, dic[i] - dic[i - 1] - a)
	print(ans)


test = int(input())
for _ in range(test):
	n = int(input())
	array = list(map(int, input().split()))
	maxi = max(array)
	index = []
	for i in range(n):
		if array[i] == maxi:
			index.append(i)
	if len(index) == 1:
		print(n // 2)
	elif index[len(index) - 1] - index[0] >= n // 2:
		print(0)
	else:
		print(n // 2 - (index[len(index) - 1] - index[0]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mid = n // 2 - 1
	max_beg = max(l)
	f_o = l.index(max_beg)
	l.reverse()
	l_o = l.index(max_beg)
	l_o = n - 1 - l_o
	if l_o - f_o >= mid:
		print(0)
	elif f_o == l_o:
		f_o = mid
		print(n - 1 - f_o)
	else:
		gap = l_o - f_o
		f_o = mid
		l_o = f_o + gap
		print(n - 1 - l_o)


from collections import defaultdict
test = int(input())
for _ in range(test):
	r = int(input())
	s = list(map(int, input().split()))
	m = max(s)
	l = int(r / 2)
	step = 0
	index = []
	for i in range(len(s)):
		if s[i] == m:
			index.append(i)
	if len(index) == 1:
		print(l)
	else:
		diff = index[-1] - index[0]
		if diff + 1 > l:
			print(0)
		else:
			print(l - diff)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	m = max(l)
	x = l.index(m)
	k = l[::-1].index(m)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	u = []
	k = 0
	t = max(l)
	for i in range(n):
		if l[i] == t:
			break
	y = i + 1
	while y != i:
		if l[y] != t:
			k += 1
		else:
			u.append(k)
			k = 0
		y = (y + 1) % n
	if k != 0:
		u.append(k)
	s = 0
	for i in range(len(u)):
		s += max(0, u[i] - n // 2 + 1)
	print(s)


for _ in range(int(input())):
	N = int(input())
	seq = list(map(int, input().split()))
	maxx = max(seq)
	count = 0
	seq = seq + seq
	max_cont = 0
	for i in range(2 * N):
		if seq[i] != maxx:
			count += 1
		else:
			if count > max_cont:
				max_cont = count
			count = 0
	if count > max_cont:
		max_cont = count
	print(max(max_cont - N // 2 + 1, 0))


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	max_index = l1.index(max(l1))
	min_index = n - l1[::-1].index(max(l1)) - 1
	if min_index - max_index > n // 2:
		print(0)
	else:
		print(n // 2 - (min_index - max_index))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	d = []
	for j in range(n):
		if l[j] == m:
			d.append(j + 1)
	d.append(d[0] + n)
	h = n // 2
	ans = 0
	for k in range(1, len(d)):
		ans += max(0, d[k] - d[k - 1] - h)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	max_1 = max(a)
	a = a + a[:n // 2 - 1]
	(start, end, res) = (0, 0, 0)
	while end < len(a):
		if a[end] == max_1:
			end += 1
			start = end + 0
		elif end - start + 1 == n / 2:
			res += 1
			end += 1
			start += 1
		else:
			end += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	x = l.index(m)
	k = l[::-1].index(m)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	m = max(a)
	ind = []
	for i in range(n):
		if a[i] == m:
			ind.append(i)
	if len(ind) == 1:
		print(n // 2)
		continue
	f = ind[0]
	l = ind[-1]
	width = l - f + 1
	if width > n // 2:
		print(0)
	else:
		print(n // 2 - width + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.index(max(l))
	b = n - l[::-1].index(max(l)) - 1
	if b - a > n // 2:
		print(0)
	else:
		print(n // 2 - (b - a))


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	N = [i for i in range(1, n + 1)]
	w = list(map(int, input().split()))
	max_sweetness = max(w)
	sizes = []
	cnt = 0
	for i in range(n):
		if w[i] != max_sweetness:
			cnt += 1
		else:
			sizes.append(cnt)
			cnt = 0
	if cnt != 0:
		sizes[0] = cnt + sizes[0]
	res = 0
	for i in range(len(sizes)):
		res += max(sizes[i] - n // 2 + 1, 0)
	print(res)


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = l.index(max(l))
	l.reverse()
	y = l.index(max(l))
	y = len(l) - y - 1
	sub = y - x
	if sub >= math.floor(n // 2):
		print(0)
	else:
		print(n // 2 - (y - x))


n = int(input())
for i in range(n):
	m = int(input())
	x = [int(p) for p in input().split()]
	j = max(x)
	p = x.index(j)
	m1 = p
	for l in range(m - 1, p + 1, -1):
		if j == x[l]:
			m1 = l
			break
	m1 = m1 - p
	if m1 >= m // 2:
		print('0')
	else:
		print(m // 2 - m1)


for __ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	x = a.index(m)
	k = a[::-1].index(m)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	(mg, t) = (0, 0)
	half = n // 2
	l = l * 2
	for i in l:
		if i < m:
			t += 1
			if mg < t:
				mg = t
		else:
			t = 0
	if mg - half >= 0:
		print(mg - half + 1)
	else:
		print(0)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	a = []
	for i in range(n):
		if m == l[i]:
			a.append(i + 1)
	b = []
	for i in range(1, len(a)):
		b.append(a[i] - a[i - 1])
	if len(a) > 1:
		b.append(n - a[-1] + a[0])
		k = max(b)
		if k >= n // 2:
			print(k - n // 2)
		else:
			print(0)
	else:
		print((n + 1) // 2)


t = int(input())
while t > 0:
	n = int(input())
	if n % 2 == 0:
		l = list(map(int, input().split()))
		a = l.index(max(l))
		b = n // 2
		c = n - l[::-1].index(max(l)) - 1
		d = abs(a - c)
		if b < d:
			print(0)
		else:
			print(b - d)
	else:
		print(0)
	t = t - 1


for i in range(int(input())):
	o = int(input())
	list5 = list(map(int, input().split()))
	index_max = list5.index(max(list5))
	index_max_rev = o - list5[::-1].index(max(list5)) - 1
	if index_max_rev - index_max > o // 2:
		print(0)
	else:
		print(o // 2 - (index_max_rev - index_max))


def answer():
	m = max(w)
	count = []
	c = 0
	for i in w:
		if i == m:
			count.append(c)
			c = -1
		c += 1
	if c:
		count.append(c)
	first = w[0] != m
	last = w[-1] != m
	if first and last:
		count[0] += count[-1]
		count.pop()
	k = 0
	for i in count:
		if i >= n // 2:
			k += i - n // 2 + 1
	return k
for T in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	print(answer())


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	maxi = max(arr)
	for i in range(n - 1, -1, -1):
		if arr[i] == maxi:
			r = i
			break
	for i in range(n):
		if arr[i] == maxi:
			r = r - i
			break
	if n // 2 - r < 0:
		print(0)
	else:
		print(n // 2 - r)


class node:

	def __init__(self, size, elements):
		self.size = size
		self.elements = elements

def solve(ele, s):
	m = max(ele)
	(i, j) = (0, 0)
	flag = True
	for k in range(s):
		if ele[k] == m:
			j = k
			if flag:
				flag = False
				i = k
	if i == j:
		return s // 2
	elif j - i >= s // 2:
		return 0
	else:
		(i, j) = (s // 2, j + s // 2 - i)
		return s - j

def __starting_point():
	t = int(input())
	inputs = []
	for i in range(t):
		inputs.append(node(int(input()), list(map(int, input().split()))))
	for i in inputs:
		print(solve(i.elements, i.size))
__starting_point()


def func(a, n):
	count = 0
	m = max(a)
	arr = []
	for i in a:
		if i != m:
			count += 1
		if i == m:
			arr.append(count)
			count = 0
	if count > 0:
		arr[0] = arr[0] + count
	l = max(arr)
	return max(l - n // 2 + 1, 0)
x = int(input())
for i in range(x):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(a, n))


for _ in range(int(input())):
	q = int(input())
	arr = list(map(int, input().split()))
	t = max(arr)
	for i in range(q - 1, -1, -1):
		if arr[i] == t:
			r = i
			break
	for i in range(q):
		if arr[i] == t:
			r = r - i
			break
	if q // (1 + 1) - r < 0:
		print(0)
	else:
		print(q // (1 + 1) - r)


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	x = a.index(m)
	k = a[::-1].index(m)
	y = n - k - 1
	if y - x >= n // 2:
		print(0)
	else:
		print(n // 2 - (y - x))
	t = t - 1


t = int(input())
for ii in range(0, t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	l = len(a)
	r = max(a)
	dp = []
	req = 0
	flag = 1
	if flag == 0:
		for i in range(0, l):
			if a[i] == r:
				dp.append(i + 1)
		if dp[0] > l // 2:
			req = req + (l - dp[-1]) + 1
		elif l - dp[-1] + dp[0] - 1 > l // 2:
			req = req + (l - dp[-1] + dp[0]) - l // 2
		k = dp[0]
		if len(dp) == n:
			print(n - 1)
			continue
		for i in range(1, len(dp)):
			if dp[i] - k > l // 2:
				req = req + dp[i] - k - l // 2
			k = dp[i]
		print(req)
	else:
		for i in range(0, l):
			if a[i] == r:
				dp.append(i + 1)
		dp2 = []
		for i in range(1, len(dp)):
			dp2.append(dp[i] - dp[i - 1] - 1)
		dp2.append(l - dp[-1] + dp[0] - 1)
		for i in dp2:
			if i >= l // 2:
				req = req + i + 1 - l // 2
		print(req)


from sys import maxsize, stdout, stdin
mod = int(1000000000.0 + 7)

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
for _ in range(I()):
	n = I()
	ls = lint()
	cnt = 0
	arr = [0] * n
	m = max(ls)
	idx = ls.index(m)
	ideal = n // 2
	shift = ideal - idx
	for i in range(n):
		arr[i] = ls[(i - shift) % n]
	if m in arr[:n // 2]:
		print(0)
	else:
		for j in range(n - 1, n // 2 - 1, -1):
			if arr[j] != m:
				cnt += 1
			else:
				break
		print(cnt + 1)


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	arr = []
	m = max(s)
	c = 0
	for i in s:
		if i != m:
			c += 1
		else:
			arr.append(c)
			c = 0
	if c != 0:
		arr[0] += c
	print(max(max(arr) - n // 2 + 1, 0))


t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	s = max(w)
	half = n // 2
	fm = w.index(s)
	lm = fm
	for i in range(fm + 1, n):
		if w[i] == s:
			lm = i
	ml = lm - fm + 1
	if ml > half:
		print(0)
	else:
		print(half - ml + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	f = a.index(m)
	l = a[::-1].index(m)
	l = n - l - 1
	diff = l - f
	if diff >= n // 2:
		print('0')
	else:
		print(n // 2 - diff)