Read problems statements in mandarin chinese, russian and vietnamese as well. 

The Chef had a box with N numbers arranged inside it: A_{1}, A_{2}, ..., A_{N}. He also had the number N at the front, so that he knows how many numbers are in it. That is, the box actually contains N+1 numbers. But in his excitement due the ongoing IOI, he started dancing with the box in his pocket, and the N+1 numbers got jumbled up. So now, he no longer knows which of the N+1 numbers is N, and which the actual numbers are.

He wants to find the largest of the N numbers. Help him find this.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
Each of the next T lines will contain N and N numbers, but it is not guaranteed that N is the first number. 

------ Output ------ 

For each test case, output a single line containing the maximum value of the N numbers in that testcase.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤  50 $
$1 ≤ A_{i} ≤ 10^{9} $

----- Sample Input 1 ------ 
3

1 2 1

3 1 2 8

1 5 1 4 3 2
----- Sample Output 1 ------ 
1

8

4
----- explanation 1 ------ 
Test case 1: 

N = 2 and the numbers are {1, 1}. The maximum among these 2 numbers is 1, and hence the output is 1. 

Test case 2:

N = 3 and the numbers are {1, 2, 8}. The maximum among these 3 numbers is 8, and hence the output is 8. 

Test case 3:

N = 5 and the numbers are {1, 1, 4, 3, 2}. The maximum among these 5 numbers is 4, and hence the output is 4.

Difficulty: EASY
Tags: Constructive algorithms

Data structures

Implementation

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for test_cases in range(int(input())):
	list_a = list(map(int, input().split()))
	length = len(list_a)
	val = length - 1
	list_a.remove(val)
	max_val = max(list_a)
	print(max_val)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	l = len(a)
	p = []
	c = a.count(l - 1)
	for i in range(l):
		if a[i] != l - 1:
			p.append(a[i])
	if c > 1:
		for k in range(c - 1):
			p.append(l - 1)
	print(max(p))


for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = len(l) - 1
	id1 = l.index(n)
	l.pop(id1)
	print(max(l))


test = int(input())
for i in range(test):
	ls = list(map(int, input().split()))
	size = len(ls)
	for i in range(size):
		if ls[i] == size - 1:
			ls[i] = 0
			break
	ans = max(ls)
	print(ans)


n = int(input())
for i in range(0, n):
	a = list(map(int, input().split()))
	a.remove(len(a) - 1)
	print(max(a))


for _ in range(int(input())):
	a = [int(x) for x in input().split()]
	b = len(a) - 1
	(m, c) = (0, 0)
	for i in a:
		if i > m:
			if i == b:
				if c:
					m = i
				else:
					c = 1
			else:
				m = i
	print(m)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = len(l) - 1
	l.sort()
	if l[-1] != n:
		print(l[-1])
	else:
		print(l[-2])


for _ in range(int(input())):
	u = list(map(int, input().split()))
	p = len(u) - 1
	u.remove(p)
	print(max(u))


def inte(e):
	return int(e)
for x in range(int(input())):
	nums = input().split()
	nums.remove(str(len(nums) - 1))
	nums.sort(reverse=True, key=inte)
	print(nums[0])


for _ in range(int(input())):
	l = list(map(int, input().split()))
	x = len(l) - 1
	l.remove(x)
	print(max(l))


t = int(input())
for i in range(t):
	l = [int(a) for a in map(int, input().split())]
	l.remove(len(l) - 1)
	print(max(l))


T = int(input())
for i in range(T):
	list = [int(x) for x in map(int, input().split())]
	k = len(list) - 1
	list.remove(k)
	print(max(list))


for i in range(int(input())):
	l = list(map(int, input().split()))
	l.remove(len(l) - 1)
	print(max(l))


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	a.sort()
	x = len(a)
	j = 0
	for j in range(x):
		if a[j] == x - 1:
			del a[j]
			break
	print(max(a))


for _ in range(int(input())):
	l = list(map(int, input().split()))
	m = len(l) - 1
	for ele in l:
		if ele == m:
			l.remove(ele)
			print(max(l))
			break


for i in range(int(input())):
	lst = list(map(int, input().split()))
	lst.sort()
	if lst[len(lst) - 1] == len(lst) - 1:
		print(lst[len(lst) - 2])
	else:
		print(lst[len(lst) - 1])


T = int(input())
for i in range(T):
	arr = list(map(int, input().split()))
	l = len(arr)
	maxT = 0
	for i in range(len(arr)):
		if arr[i] == l - 1:
			n = arr[i]
			arr.pop(i)
			break
	for i in range(n):
		if arr[i] > maxT:
			maxT = arr[i]
	print(maxT)


t = int(input())
for i in range(t):
	n = list(map(int, input().split()))
	a = len(n) - 1
	n.remove(a)
	b = max(n)
	print(b)


a = int(input(''))
for i in range(a):
	t = [int(x) for x in input('').split()]
	k = list(t)
	g = len(k) - 1
	k.remove(g)
	print(max(k))


t = int(input())
for i in range(t):
	l = [int(i) for i in input().split()]
	for i in l:
		if i == len(l) - 1:
			l.remove(i)
			break
	print(max(l))


for _ in range(int(input())):
	list_a = list(map(int, input().split()))
	list_a.remove(len(list_a) - 1)
	print(max(list_a))


t = int(input())
for i in range(t):
	num = list(map(int, input().split()))
	length = len(num)
	num.remove(length - 1)
	print(max(num))


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	slen = len(l)
	l.remove(slen - 1)
	print(max(l))


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


t = int(input())
while t > 0:
	l = list(map(int, input().split()))
	n = len(l) - 1
	l.remove(n)
	print(max(l))
	t -= 1


t = int(input())
for _ in range(t):
	lst = list(map(int, input().split()))
	lst.remove(len(lst) - 1)
	print(max(lst))


t = int(input())
for i in range(0, t):
	s = list(map(int, input().split(' ')))
	for i in range(len(s)):
		if s[i] == len(s) - 1:
			n = s[i]
			s.remove(n)
			break
	print(max(s))


t = int(input())
for i in range(t):
	A = sorted(list(map(int, input().split())))
	if A[-1] == len(A) - 1:
		print(A[-2])
	else:
		print(A[-1])


t = int(input())
for i in range(t):
	arr = list(map(int, input().split(' ')))
	n = len(arr) - 1
	arr.remove(n)
	print(max(arr))


for _ in range(int(input())):
	a = [int(x) for x in input().split()]
	a.remove(len(a) - 1)
	print(max(a))


t = int(input())
while t:
	lst = list(map(int, input().split()))
	x = len(lst) - 1
	lst.remove(x)
	print(max(lst))
	t -= 1


t = int(input())
for test_cases in range(t):
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	if a[0] != len(a) - 1:
		print(a[0])
	else:
		print(a[1])


for _ in range(int(input())):
	l = list(map(int, input().split()))
	l = sorted(l)
	l.remove(len(l) - 1)
	print(l.pop())


for i in range(int(input())):
	a = list(map(int, input().split()))
	s = len(a) - 1
	a.remove(s)
	print(max(a))


n = int(input())
for i in range(n):
	x = list(map(int, input().split()))
	y = len(x)
	x.remove(y - 1)
	x.sort()
	print(x[y - 2])


for _ in range(int(input())):
	numbers = list(map(int, input().split()))
	length = len(numbers) - 1
	numbers.remove(length)
	numbers.sort(reverse=True)
	print(numbers[0])


for _ in range(int(input())):
	numbers = list(map(int, input().split()))
	total = len(numbers)
	numbers.remove(total - 1)
	numbers.sort()
	print(numbers[-1])


for _ in range(int(input())):
	l = list(map(int, input().split()))
	length = len(l) - 1
	l = sorted(l)
	max_nu = max(l)
	if max(l) == length:
		print(l[-2])
	else:
		print(l[-1])


for _ in range(int(input())):
	l = list(map(int, input().split()))
	l.sort()
	lg = len(l) - 1
	if lg == l[lg]:
		print(l[lg - 1])
	else:
		print(l[lg])


t = input()
for c in range(0, int(t)):
	a = list(map(int, input().split()))
	a.sort()
	out = len(a) - 1
	if out == a[len(a) - 1]:
		print(a[out - 1])
	else:
		print(a[out])


def binary_search(list, num):
	(high, low) = (len(list) - 1, 0)
	while True:
		mid = (high + low) // 2
		if list[high] == num:
			return high
		if list[low] == num:
			return low
		if list[mid] == num:
			return mid
		if list[mid] < num:
			low = mid
		if list[mid] > num:
			high = mid

def solve():
	l1 = [int(i) for i in input().split()]
	num = len(l1) - 1
	l1 = sorted(l1)
	l1.pop(binary_search(l1, num))
	return max(l1)
t = int(input())
for i in range(t):
	print(solve())


n = int(input())
for i in range(n):
	l = list(map(int, input().split(' ')))
	ln = len(l)
	for j in range(ln):
		if l[j] == ln - 1:
			l.remove(l[j])
			break
	print(max(l))


for T in range(int(input())):
	l = [int(x) for x in input().split()]
	lent = len(l)
	x = l.pop(l.index(lent - 1))
	l.sort()
	print(l[-1])


def main():
	testcases = int(input())
	i = 0
	while i < testcases:
		numbers = input().split()
		for j in range(len(numbers)):
			numbers[j] = int(numbers[j])
		removed = len(numbers) - 1
		numbers.remove(removed)
		maximum = None
		for number in numbers:
			if maximum is None:
				maximum = number
			elif number > maximum:
				maximum = number
		print(maximum)
		i += 1
main()


t = int(input())
for _ in range(t):
	n = input()
	n = n.split()
	for i in range(len(n)):
		n[i] = int(n[i])
	n.remove(len(n) - 1)
	print(max(n))


for i in range(int(input())):
	x = list(map(int, input().split(' ')))
	c = int(len(x))
	for m in x:
		if m == c - 1:
			x.remove(m)
			break
	print(max(x))


for _ in range(int(input())):
	numbers = list(map(int, input().split(' ')))
	length = len(numbers)
	n = 0
	for i in range(length):
		if numbers[i] < length and numbers[i] > n:
			n = numbers[i]
			index = i
	numbers.remove(n)
	print(max(numbers))


n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	z = len(a) - 1
	if z in a:
		a.remove(z)
	print(max(a))


for _ in range(int(input())):
	lst = list(map(int, input().split()))
	ls = list()
	f = 0
	for i in lst:
		if i == len(lst) - 1 and f == 0:
			f = 1
			continue
		ls.append(i)
	max = 0
	for j in ls:
		if j >= max:
			max = j
	print(max)


t = int(input())
while t:
	N = list(map(int, input().split()))
	N.remove(len(N) - 1)
	print(max(N))
	t = t - 1


for _ in range(int(input())):
	arr = [int(j) for j in input().split()]
	n = len(arr) - 1
	del arr[arr.index(n)]
	print(max(arr))


for _ in range(int(input())):
	arr = list((int(i) for i in input().split()))
	l = len(arr) - 1
	arr.remove(l)
	print(max(arr))


t = int(input())
for i in range(t):
	inp = input()
	l = inp.split()
	length = len(l)
	for k in range(length):
		l[k] = int(l[k])
	n = length - 1
	l.remove(n)
	l.sort()
	print(l[len(l) - 1])


for _ in range(int(input())):
	n = list(map(int, input().split()))
	for i in n:
		if i == len(n) - 1:
			n.remove(i)
			break
	print(max(n))


tests = int(input())
for i in range(tests):
	arr = list(map(int, input().split()))
	maximum = 0
	second_maximum = 0
	for j in arr:
		if j > maximum:
			second_maximum = maximum
			maximum = j
		elif j > second_maximum:
			second_maximum = j
	if len(arr) - 1 == maximum:
		print(second_maximum)
	else:
		print(maximum)


T = int(input())
for i in range(T):
	ll = list(map(int, input().split()))
	for i in range(len(ll)):
		if ll[i] == len(ll) - 1:
			ll[i] = -999
			break
	print(max(ll))


for _ in range(int(input())):
	arr = [int(x) for x in input().split(' ')]
	l1 = len(arr)
	arr.remove(l1 - 1)
	print(max(arr))


for _ in range(int(input())):
	y = list(map(int, input().split()))
	k = len(y) - 1
	y.remove(k)
	print(max(y))