Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Chef is participating in an ICPC regional contest, in which there is a total of $N$ problems (numbered $1$ through $N$) with varying difficulties. For each valid $i$, the $i$-th easiest problem is problem $A_{i}$.

After a team solves a problem, a balloon with a colour representing that problem is tied next to their desk. Chef is fond of colours in VIBGYOR, which are representative of the problems with numbers $1$ through $7$. The remaining problems have their own representative colours too.

Find the minimum number of problems which Chef's team needs to solve in order to get all the balloons for problems $1$ through $7$ (and possibly some other balloons too) tied next to their desk, if you know that Chef's team knows the difficulties of all problems and solves the problems in increasing order of difficulty.

------  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 number of problems Chef's team needs to solve.

------  Constraints ------
$1 ≤ T ≤ 10,500$
$7 ≤ N ≤ 15$
$1 ≤ A_{i} ≤ N$ for each valid $i$
$A_{1}, A_{2}, \ldots, A_{N}$ are pairwise distinct

----- Sample Input 1 ------ 
3
7
1 2 3 4 5 7 6
8
8 7 6 5 4 3 2 1
9
7 4 3 5 6 1 8 2 9
----- Sample Output 1 ------ 
7
8
8
----- explanation 1 ------ 
Example case 1: Since there are a total of $7$ problems, Chef's team will have to solve all of them.

Example case 2: Problems $1$ through $7$ appear among the first $8$ problems.

Example case 3: Problems $1$ through $7$ again appear among the first $8$ problems.

Difficulty: EASY
Tags: Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
cases = int(input())
for _ in range(cases):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if arr[i] <= 7:
			count += 1
		if count == 7:
			print(i + 1)
			break


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [1, 2, 3, 4, 5, 6, 7]
	c = 0
	for k in range(n):
		if l[k] > 0 and l[k] < 8:
			c = k + 1
	print(c)


T = int(input())
for i in range(T):
	n = int(input())
	problems = list(map(int, input().split()))
	sum = 28
	problems_solved = 0
	for x in range(n):
		if problems[x] <= 7:
			sum -= problems[x]
		if sum == 0:
			problems_solved = x + 1
			break
	print(problems_solved)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r, c) = ([1, 2, 3, 4, 5, 6, 7], 0, 0)
	for i in a:
		if r == 7:
			break
		if i in l:
			c += 1
			r += 1
		elif r != 7:
			c += 1
	print(c)


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	x = [1, 2, 3, 4, 5, 6, 7]
	p = []
	for j in range(7):
		for i in range(a):
			if x[j] == l[i]:
				p.append(i)
	print(max(p) + 1)


for _ in range(int(input())):
	n = int(input())
	a1 = list(map(int, input().split()))
	for (i, x) in enumerate(a1[::-1]):
		if x <= 7:
			print(n - i)
			break


for _ in range(0, int(input())):
	a = int(input())
	b = [int(x) for x in input().split(' ')]
	c = [1, 2, 3, 4, 5, 6, 7]
	count = 0
	for i in b:
		if c == []:
			break
		elif i in c:
			c.remove(i)
			count = count + 1
		else:
			count = count + 1
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = 0
	count = 0
	l = [1, 2, 3, 4, 5, 6, 7]
	for j in a:
		if total < 28:
			if j in l:
				total += j
			count += 1
		else:
			break
	print(count)


for i in range(int(input())):
	n = int(input())
	(arr, count) = (tuple(map(int, input().split())), 0)
	for i in range(n):
		if arr[i] <= 7:
			count += 1
		if count == 7:
			print(i + 1)
			break


t = int(input())
b = []
a = []
for i in range(t):
	b = [1, 2, 3, 4, 5, 6, 7]
	count = 0
	n = int(input())
	a = list(map(int, input().split()))
	while True:
		for j in range(n):
			if len(b) != 0:
				if a[j] in b:
					count = count + 1
					b.remove(a[j])
				else:
					count = count + 1
			else:
				break
		print(count)
		break


def sol(arr):
	nums = [1, 2, 3, 4, 5, 6, 7]
	for i in range(leng, -1, -1):
		if arr[i] in nums:
			return i + 1
for i in range(int(input())):
	leng = int(input()) - 1
	arr = input().split()
	arr = [int(i) for i in arr]
	print(sol(arr))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	set_a = {1, 2, 3, 4, 5, 6, 7}
	set_b = set()
	count = 1
	for i in a:
		set_b.add(i)
		if set_a - set_b == set():
			print(count)
			break
		else:
			count += 1


n = int(input())
for _ in range(n):
	k = int(input())
	lis = list(map(int, input().split()))
	st = set()
	count = 0
	for i in lis:
		if i >= 1 and i <= 7:
			st.add(i)
		if len(st) == 7:
			break
		count += 1
	print(count + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sums = 28
	c = 0
	for x in range(n):
		if l[x] <= 7:
			sums -= l[x]
		if sums == 0:
			c = x + 1
			break
	print(c)


for i in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	count = 0
	l = list()
	for e in q:
		if count == 7:
			break
		elif e <= 7:
			l.append(e)
			count += 1
		else:
			l.append(e)
	print(len(l))


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	sum = 28
	ps = 0
	for x in range(n):
		if p[x] <= 7:
			sum -= p[x]
		if sum == 0:
			ps = x + 1
			break
	print(ps)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(n - 1, -1, -1):
		if a[i] < 8:
			print(i + 1)
			break


z = int(input())
for i in range(z):
	m = int(input())
	p = list(map(int, input().split()))
	sum = 28
	p_s = 0
	for x in range(m):
		if p[x] <= 7:
			sum -= p[x]
		if sum == 0:
			p_s = x + 1
			break
	print(p_s)


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


t = int(input())
for i in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	check = [1, 2, 3, 4, 5, 6, 7]
	output = 0
	for i in range(len(list1) - 1, -1, -1):
		if list1[i] in check:
			output = i + 1
			break
	print(output)


test = int(input())
for i in range(test):
	num = int(input())
	arr = list(map(int, input().split()))
	count = 0
	List = [1, 2, 3, 4, 5, 6, 7]
	i = 0
	while len(List) != 0:
		count += 1
		if arr[i] in List:
			List.remove(arr[i])
		i += 1
	print(count)


def s(l):
	i = 0
	tr = [1, 2, 3, 4, 5, 6, 7]
	while True:
		if l[i] in tr:
			tr.remove(l[i])
		if tr == []:
			return i + 1
		else:
			i += 1
t = int(input())
for i in range(t):
	n = int(input())
	print(s(list(map(int, input().split()))))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	count = 0
	l = [1, 2, 3, 4, 5, 6, 7]
	i = 0
	while len(l) != 0:
		count += 1
		if arr[i] in l:
			l.remove(arr[i])
		i += 1
	print(count)


import array as arr
t = int(input())
for q in range(t):
	n = int(input())
	A = list(map(int, input().strip().split()))[:n]
	a = arr.array('i', A)
	count = 0
	for i in range(n):
		if a[i] in range(0, 8):
			count += 1
		if count == 7:
			print(i + 1)
			break


T = int(input())
for i in range(T):
	n = int(input())
	s = list(map(int, input().split()))
	sum = 28
	c = 0
	for x in range(n):
		if s[x] <= 7:
			sum -= s[x]
		if sum == 0:
			c = x + 1
			break
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = [x for x in range(1, 8)]
	l2 = list(map(int, input().split()))
	cnt = 0
	a = 0
	while l1:
		if l2[a] in l1:
			l1.remove(l2[a])
		a += 1
		cnt += 1
	print(cnt)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = [int(x) for x in input().split()]
	d = {}
	for i in range(len(l)):
		d[l[i]] = i
	max_p = -1
	for i in range(1, 8):
		max_p = max(max_p, d[i])
	print(max_p + 1)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = [1, 2, 3, 4, 5, 6, 7]
	count = 0
	for j in b:
		if len(c) > 0:
			count += 1
			if j in c:
				c.remove(j)
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(1, 8):
		c = l.index(i)
		if c > k:
			k = c
	print(k + 1)


for _ in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	c = 0
	l = [1, 2, 3, 4, 5, 6, 7]
	for i in lst:
		if i in l:
			l.remove(i)
			c += 1
			if l == []:
				break
		else:
			c += 1
	print(c)


for i in range(int(input())):
	N = int(input())
	Ai = list(map(int, input().split()))
	VBG = []
	for i in range(1, 8):
		VBG.append(Ai.index(i))
	print(max(VBG) + 1)


T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	l1 = []
	for i in range(len(arr)):
		if arr[i] <= 7:
			l1.append(i)
	print(max(l1) + 1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	num = 0
	index = 0
	for i in range(n):
		if 1 <= a[i] <= 7:
			num += 1
		if num == 7:
			index = i + 1
			break
	print(index)


for _ in range(int(input())):
	n = int(input())
	(a, c) = (tuple(map(int, input().split())), 0)
	for i in range(n):
		if a[i] <= 7:
			c += 1
		if c == 7:
			print(i + 1)
			break


t = int(input())
for i in range(t):
	n = int(input())
	problemas = list(map(int, input().split()))
	sum = 28
	problemas_resueltos = 0
	for x in range(n):
		if problemas[x] <= 7:
			sum -= problemas[x]
		if sum == 0:
			problemas_resueltos = x + 1
			break
	print(problemas_resueltos)


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	n = [1, 2, 3, 4, 5, 6, 7]
	c = 0
	for i in l:
		if i in n:
			n.remove(i)
		c += 1
		if n == []:
			break
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	l = []
	for i in a:
		if c == 7:
			break
		elif i <= 7:
			l.append(i)
			c += 1
		else:
			l.append(i)
	print(len(l))


s = int(input())
for i in range(s):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if l[i] <= 7:
			c = c + 1
		if c == 7:
			print(i + 1)
			break


for i in range(int(input())):
	N = int(input())
	li = [int(x) for x in input().split(' ', N)]
	a = []
	for m in range(1, 8):
		a.append(li.index(m))
	print(max(a) + 1)


for _ in range(int(input())):
	buddy = int(input())
	(arr, count) = (tuple(map(int, input().split())), 0)
	for v in range(buddy):
		if arr[v] <= 7:
			count += 1
		if count == 7:
			print(v + 1)
			break


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	t = 7
	count = 0
	for i in range(n):
		if a[i] >= 1 and a[i] <= 7:
			t -= 1
			count += 1
			if t == 0:
				break
		else:
			count += 1
	print(count)


l = [i for i in range(1, 8)]
for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for j in range(len(A)):
		if A[j] in l:
			ans += 1
			if ans == 7:
				print(j + 1)
				break


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 28
	p_s = 0
	for k in range(n):
		if a[k] <= 7:
			sum = sum - a[k]
		if sum == 0:
			p_s = k + 1
			break
	print(p_s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	d = 0
	for i in range(len(a)):
		if a[i] <= 7:
			c += 1
		if c == 7:
			d = i + 1
			break
	print(d)


def Ans(n, lst):
	j = 0
	for i in range(n):
		if j == 7:
			return i
		elif lst[i] >= 1 and lst[i] <= 7:
			j += 1
		else:
			continue
	return n
for _ in range(int(input())):
	n = int(input())
	lst = [int(item) for item in input().split()]
	print(Ans(n, lst))


t = int(input())
c = [1, 2, 3, 4, 5, 6, 7]
for i in range(t):
	p = 0
	s = 0
	n = int(input())
	l = list(map(int, input().split()))
	for j in l:
		if j in c:
			p = p + 1
		elif j not in c and p < 7:
			s = s + 1
	print(p + s)


for _ in range(int(input())):
	cols = int(input())
	blun = list(map(int, input().split()))
	j = 0
	for i in range(cols):
		j = cols - i - 1
		if blun[j] < 8:
			break
	print(j + 1)


t = int(input())
while t > 0:
	count1 = 0
	count = 0
	n = int(input())
	l = list(map(int, input().strip().split()))
	for i in range(n):
		if l[i] >= 1 and l[i] <= 7:
			count += 1
			if count == 7:
				break
		else:
			count1 += 1
	print(count + count1)
	t -= 1


b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	h = [1, 2, 3, 4, 5, 6, 7]
	l = 0
	for i in a:
		if h == []:
			break
		elif i <= 7:
			l = l + 1
			h.remove(i)
		else:
			l = l + 1
	print(l)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for j in range(n):
		if l[j] >= 1 and l[j] <= 7:
			k += 1
		if k >= 7:
			print(j + 1)
			break


x = [1, 2, 3, 4, 5, 6, 7]
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	b = 0
	for j in range(n):
		if c == 7:
			break
		if a[j] in x:
			c += 1
		b += 1
	print(b)


for _ in range(int(input())):
	n = int(input())
	prob = list(map(int, input().split()))
	ans = 28
	prob_solve = 0
	for i in range(n):
		if prob[i] <= 7:
			ans -= prob[i]
		if ans == 0:
			prob_solve = i + 1
			break
	print(prob_solve)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	num = [1, 2, 3, 4, 5, 6, 7]
	count1 = 0
	count2 = 0
	for i in range(N):
		if A[i] in num:
			count1 += 1
			if count1 == 7:
				break
		count2 += 1
	print(count2 + 1)


count = 0
iter_ = 0
for i in range(int(input())):
	num_ = int(input())
	values = list(map(lambda x: int(x), input().split(' ')))
	for value in values:
		if count == 7:
			break
		if value in range(1, 8):
			count += 1
			iter_ += 1
			continue
		iter_ += 1
	print(iter_)
	count = 0
	iter_ = 0


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	i = len(nums) - 1
	while i >= 0:
		if nums[i] >= 1 and nums[i] <= 7:
			break
		i -= 1
	print(i + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = []
	c1 = 0
	c = 0
	for i in range(0, n):
		if l[i] == 1 or l[i] == 2 or l[i] == 3 or (l[i] == 4) or (l[i] == 5) or (l[i] == 6) or (l[i] == 7):
			k.append(i)
	p = max(k)
	print(p + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(0, n):
		if l[i] in range(1, 8):
			l[i] = 0
	l = l[::-1]
	s = l.index(0)
	print(len(l[s:]))


for i in range(int(input())):
	n = int(input())
	lik = list(map(int, input().split()))
	sol = [1, 2, 3, 4, 5, 6, 7]
	ans = []
	for i in range(len(lik)):
		ans.append(lik[i])
		ans.sort()
		if len(ans) >= 7 and sol == ans[0:7]:
			break
	print(len(ans))


for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	total = 0
	for i in a:
		if 1 <= i <= 7:
			count += 1
		total += 1
		if count == 7:
			break
	print(total)


for i in range(int(input())):
	n = int(input())
	count = 0
	ans = 0
	j = 0
	ques = list(map(int, input().split(' ')))
	if n == 7:
		print(7)
	else:
		while count < 7:
			if ques[j] == 1 or ques[j] == 2 or ques[j] == 3 or (ques[j] == 4) or (ques[j] == 5) or (ques[j] == 6) or (ques[j] == 7):
				count = count + 1
			ans = ans + 1
			j = j + 1
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [1, 2, 3, 4, 5, 6, 7]
	for i in range(len(a)):
		if a[i] < 8:
			if b[a[i] - 1] != 0:
				b[a[i] - 1] = 0
		if b.count(0) == 7:
			print(i + 1)
			break


for i in range(int(input())):
	n = int(input())
	lt = list(map(int, input().split()))
	sol = [1, 2, 3, 4, 5, 6, 7]
	res = []
	lt2 = []
	for i in range(len(lt)):
		res.append(lt[i])
		if len(res) >= 7:
			lt2 = res.copy()
			lt2.sort()
			if sol == lt2[0:7]:
				break
	print(len(res))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = [1, 2, 3, 4, 5, 6, 7]
	c = 0
	for j in range(len(l) - 1, -1, -1):
		if l[j] in m:
			print(j + 1)
			break


for i in range(int(input())):
	n = int(input())
	s = input().split()
	count = 0
	l = ['1', '2', '3', '4', '5', '6', '7']
	for i in s:
		if len(l) == 0:
			break
		count += 1
		if i in l:
			l.remove(i)
	print(count)


a = int(input())
for i in range(a):
	done = int(input())
	l = list(map(int, input().strip().split()))[:done]
	a = 0
	h = 0
	for j in l:
		h += 1
		if j <= 7:
			a += 1
			if a == 7:
				print(h)
				break