Chef has an array A of length N. Chef wants to select some disjoint, non-empty subarrays from A such that:
The mex of each of the selected subarray is the same. 

Note that the selected subarrays need not cover all the elements of the array.

For e.g. if A = [2, 0, 1, 6, 2, 1, 3, 0, 7], then one way in which Chef can select subarrays is as following: {[0, 1], [1, 3, 0]} (Here mex of both of them is 2).

Chef wants to select the maximum number of disjoint, non-empty subarrays that satisfy the above condition. Can you help him to do so?

Note: An array X is called a subarray of an array Y if X can be obtained from Y by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Also, mex of a subarray is the smallest non-negative number that does not occur in that subarray.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N - the length of the array A.
- The second line of each test case contains N space-separated integers - A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the maximum number of disjoint subarrays which Chef can select such that mex of each subarray is the same.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤A_{i} ≤N$
- It is guaranteed that the sum of $N$ does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
4
0 1 1 0
6
0 0 3 1 2 0

----- Sample Output 1 ------ 
2
3

----- explanation 1 ------ 
Test case-1: Chef can select the following subarrays: $[0, 1]$, $[1, 0]$. Here $mex([0, 1]) = mex([1, 0]) = 2$. Therefore the answer is $2$.

Test case-2: Chef can select the following subarrays: $[0]$, $[0, 3]$, $[2, 0]$. Here $mex([0]) = mex([0, 3]) = mex([2, 0]) = 1$. Therefore the answer is $3$.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(b, c) = (0, 0)
	for i in a:
		if i:
			c += 1
		else:
			b += 1
	print(max(b, c))


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	z = 0
	for ele in arr:
		if ele == 0:
			z += 1
	rem = n - z
	print(z if z > rem else rem)


t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	xl = Counter(lst)
	if xl[0] > n - xl[0]:
		print(xl[0])
	else:
		print(n - xl[0])


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	zeroes = arr.count(0)
	rem = n - zeroes
	if zeroes > rem:
		print(zeroes)
	else:
		print(rem)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	zero = l.count(0)
	other = n - zero
	if zero < other:
		print(other)
	else:
		print(zero)


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = 0
	for ii in b:
		if ii == 0:
			c += 1
	print(max(c, a - c))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	m = a.count(0)
	print(max(m, n - m))
	t -= 1


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	z = 0
	for i in l:
		if i == 0:
			z += 1
	print(max(z, n - z))


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


n = int(input())
for i in range(0, n):
	a = int(input())
	l = input().split()
	count = 0
	for j in range(0, a):
		l[j] = int(l[j])
	for k in range(0, a):
		if l[k] == 0:
			count = count + 1
	print(max(count, a - count))


def solve(a, n):
	x = a.count(0)
	return max(x, n - x)
for _ in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	print(solve(a, n))


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


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	if N == 1:
		print(1)
		continue
	zeros = A.count(0)
	if zeros == 0:
		print(N)
		continue
	if zeros == N:
		print(N)
		continue
	ans = max(N - zeros, zeros)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count_0 = arr.count(0)
	L = len(arr)
	print(max(count_0, L - count_0))


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	zeroes = arr.count(0)
	print(max(zeroes, length - zeroes))


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


for _ in range(int(input())):
	N = int(input())
	A = len([int(s) for s in input().split() if s != '0'])
	print(max(A, N - A))


T = int(input())
for i in range(0, T):
	a = int(input())
	b = input().split()
	bb = 0
	for j in b:
		if j == '0':
			bb += 1
	print(max(bb, a - bb))


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	z = li.count(0)
	print(max(z, len(li) - z))


for _ in range(int(input())):
	n = int(input())
	nums = input().split()
	count0 = nums.count('0')
	print(max(count0, n - count0))


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


for _ in range(int(input())):
	N = int(input())
	li = list(map(int, input().split()))
	print(max(li.count(0), N - li.count(0)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	count1 = 0
	count2 = 0
	for i in range(n):
		if a[i] != 0:
			count1 += 1
		else:
			count2 += 1
	if count1 == count2:
		print(count1)
	else:
		print(max(count1, count2))


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


case = int(input())
for i in range(case):
	N = int(input())
	li = list(map(int, input().split(' ')))
	count = 0
	for j in li:
		if j == 0:
			count += 1
	ans = max(count, N - count)
	print(ans)


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


tl = int(input())
while tl:
	tl -= 1
	f = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		if i == 0:
			c += 1
	print(max(c, f - c))


n = int(input())
for _ in range(n):
	m = int(input())
	a = list(map(int, input().split(' ')))
	v = a.count(0)
	ans = max(v, m - v)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split(' ')))
	x = arr.count(0)
	ans = max(x, N - x)
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	p = a.count(0)
	if p > len(a) // 2:
		print(p)
	else:
		print(len(a) - p)
	t -= 1


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	A.sort()
	d = dict()
	if 0 not in A:
		print(n)
		continue
	z = A.count(0)
	print(max(z, n - z))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	z = l1.count(0)
	k = max(z, n - z)
	print(k)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(len(a)):
		if a[i] == 0:
			count += 1
	print(max(count, n - count))


try:
	t = int(input())
	for i in range(t):
		num = int(input())
		lst = list(map(int, input().split()))
		c = 0
		for i in range(len(lst)):
			if lst[i] == 0:
				c += 1
		print(max(c, num - c))
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(zeros, non_zeros) = (0, 0)
	for i in a:
		if i == 0:
			zeros += 1
		else:
			non_zeros += 1
	print(max(non_zeros, zeros))


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	x = a.count(0)
	if x > n - x:
		print(x)
	else:
		print(n - x)


T = int(input())
for cases in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	c = l.count(0)
	res = N - c
	print(max(res, c))


t = int(input())
for cases in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = l.count(0)
	re = n - x
	print(max(re, x))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cz = arr.count(0)
	print(max(cz, len(arr) - cz))


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


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if a[i] == 0:
			c += 1
	print(max(c, n - c))
t = int(input())
while t > 0:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	x = input()
	arr = [int(z) for z in x.split(' ')]
	zero = 0
	pos = 0
	for i in arr:
		if i == 0:
			zero += 1
		else:
			pos += 1
	print(max(zero, pos))


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(N):
		if arr[i] == 0:
			count += 1
	print(max(N - count, count))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(max(a.count(0), n - a.count(0)))


try:
	for _ in range(int(input())):
		n = int(input())
		A = list(map(int, input().split()))[:n]
		(mex1, mex2) = (0, 0)
		for e in A:
			if e == 0:
				mex1 += 1
			else:
				mex2 += 1
		print(max(mex1, mex2))
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	li = list(map(int, input().split()))
	p = li.count(0)
	if n - p > p:
		print(n - p)
	else:
		print(p)
	t = t - 1


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(inp())
	a = [int(i) for i in input().split()]
	print(max(a.count(0), n - a.count(0)))


ans = ''
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = arr.count(0)
	maxcount = max(cnt, n - cnt)
	ans += str(maxcount) + '\n'
print(ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	zeroes = arr.count(0)
	if zeroes > len(arr) - zeroes:
		print(zeroes)
	else:
		print(len(arr) - zeroes)
	t -= 1