Who's interested in football?
Rayne Wooney has been one of the top players for his football club for the last few years. But unfortunately, he got injured during a game a few months back and has been out of play ever since.
He's got proper treatment and is eager to go out and play for his team again. Before doing that, he has to prove to his fitness to the coach and manager of the team. Rayne has been playing practice matches for the past few days. He's played N practice matches in all.
He wants to convince the coach and the manager that he's improved over time and that his injury no longer affects his game. To increase his chances of getting back into the team, he's decided to show them stats of any 2 of his practice games. The coach and manager will look into the goals scored in both the games and see how much he's improved. If the number of goals scored in the 2nd game(the game which took place later) is greater than that in 1st, then he has a chance of getting in. Tell Rayne what is the maximum improvement in terms of goal difference that he can show to maximize his chances of getting into the team. If he hasn't improved over time, he's not fit to play. Scoring equal number of goals in 2 matches will not be considered an improvement. Also, he will be declared unfit if he doesn't have enough matches to show an improvement.

------ Input: ------ 

The first line of the input contains a single integer T, the number of test cases.
Each test case begins with a single integer N, the number of practice matches Rayne has played.

The next line contains N integers. The ith integer, gi, on this line represents the number of goals Rayne scored in his ith practice match. The matches are given in chronological order i.e. j > i means match number j took place after match number i.

------ Output: ------ 

For each test case output a single line containing the maximum goal difference that Rayne can show to his coach and manager. If he's not fit yet, print "UNFIT".

------ Constraints: ------ 

1≤T≤10

1≤N≤100000

0≤gi≤1000000 (Well, Rayne's a legend! You can expect him to score so many goals!)

----- Sample Input 1 ------ 
3
6
3 7 1 4 2 4
5
5 4 3 2 1
5
4 3 2 2 3
----- Sample Output 1 ------ 
4
UNFIT
1
----- explanation 1 ------ 
In the first test case, Rayne can choose the first and second game. Thus he gets a difference of 7-3=4 goals. Any other pair would give him a lower improvement.
In the second test case, Rayne has not been improving in any match. Thus he's declared UNFIT.
Note: Large input data. Use faster I/O methods. Prefer scanf,printf over cin/cout.

Difficulty: MEDIUM
Tags: Dynamic programming

Constructive algorithms

Data structures

Ad-hoc
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	i = 1
	s = x[0]
	b = 0
	m = 0
	while i < n:
		if x[i] < x[i - 1]:
			s = min(s, x[i])
			i += 1
		else:
			m = max(m, x[i] - s)
			i += 1
	if m == 0:
		print('UNFIT')
	else:
		print(m)


t = input()
for c in range(0, int(t)):
	n = input()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	diff = 0
	mi = 0
	for y in range(0, int(n)):
		if y > 0:
			if arr[y] - arr[mi] > diff:
				diff = arr[y] - arr[mi]
		if arr[y] < arr[mi]:
			mi = y
	if diff > 0:
		print(diff)
	else:
		print('UNFIT')


for _ in range(int(input())):
	n = int(input())
	g = list(map(int, input().split()))
	c = g[0]
	p = 0
	if n == 1:
		print('UNFIT')
		continue
	for i in range(1, n):
		x = g[i]
		if x < c:
			c = x
		else:
			p = max(p, x - c)
	if p:
		print(p)
	else:
		print('UNFIT')


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	netmax = 0
	mini = a[0]
	for x in a:
		netmax = max(netmax, x - mini)
		mini = min(mini, x)
	print(netmax if netmax > 0 else 'UNFIT')


T = int(input())
for x in range(T):
	N = int(input())
	goals = list(map(int, input().split()))
	b = list()
	c = list()
	b.append(goals[0])
	c.append(goals[N - 1])
	ele = goals[0]
	for i in range(1, N):
		ele = min(goals[i], ele)
		b.append(ele)
	ele = goals[N - 1]
	for i in range(2, N + 1):
		ele = max(goals[N - i], ele)
		c.append(ele)
	ele = 0
	for i in range(N):
		ele = max(ele, c[i] - b[N - 1 - i])
	if ele == 0:
		print('UNFIT')
	else:
		print(ele)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	score = 0
	i = 1
	S = A[0]
	while i < N:
		if A[i] < A[i - 1]:
			S = min(S, A[i])
			i += 1
		else:
			score = max(score, A[i] - S)
			i += 1
	if score == 0:
		print('UNFIT')
	else:
		print(score)


for test in range(int(input())):
	N = int(input())
	list = input().split()
	list = [eval(i) for i in list]
	dif = 0
	small = list[0]
	for i in range(len(list) - 1):
		if list[i + 1] < list[i]:
			small = min(small, list[i + 1])
		else:
			dif = max(dif, list[i + 1] - small)
	if dif >= 1:
		print(dif)
	else:
		print('UNFIT')


for i in range(int(input())):
	N = int(input())
	games = list(map(int, input().split()))
	smin = games[0]
	c = 0
	for i in range(1, N):
		if games[i] > smin:
			c = max(c, games[i] - smin)
		else:
			smin = games[i]
	if c == 0:
		print('UNFIT')
	else:
		print(c)


for _ in range(int(input())):
	n = int(input())
	gi = list(map(int, input().split()))
	start = gi[0]
	result = 0
	i = 0
	while i < n - 1:
		if gi[i + 1] < gi[i]:
			start = min(start, gi[i + 1])
			i += 1
		else:
			result = max(result, gi[i + 1] - start)
			i += 1
	print('UNFIT') if result == 0 else print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	goals = list(map(int, input().split()))
	if n >= 2:
		mini = goals[0]
		out = -1
		for i in goals[1:]:
			diff = i - mini
			if diff > out:
				out = diff
			if i < mini:
				mini = i
		if out > 0:
			print(out)
		else:
			print('UNFIT')
	else:
		print('UNFIT')


for I in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	c = 0
	if n == 1:
		print('UNFIT')
	else:
		for i in range(1, n):
			if a[i] - x > c:
				c = a[i] - x
			if a[i] < x:
				x = a[i]
		if c > 0:
			print(c)
		else:
			print('UNFIT')


t = int(input())
for i in range(0, t, 1):
	n = int(input())
	nums = list(map(int, input().strip().split()))[:n]
	min_val = float('inf')
	diff = -1 * float('inf')
	for i in range(0, n, 1):
		min_val = min(min_val, nums[i])
		if i >= 1:
			diff = max(diff, nums[i] - min_val)
	if diff > 0:
		print(diff)
	else:
		print('UNFIT')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	maxi = []
	cur = arr[-1]
	for i in range(n - 1, -1, -1):
		cur = max(cur, arr[i])
		maxi.append(cur)
	maxi = maxi[::-1]
	ans = -1
	for i in range(n - 1):
		ans = max(ans, maxi[i] - arr[i])
	if ans <= 0 or n == 1:
		print('UNFIT')
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	g = [int(x) for x in input().split()]
	x = g[0]
	c = 0
	if n == 1:
		print('UNFIT')
	else:
		for j in range(1, n):
			if g[j] - x > c:
				c = g[j] - x
			if g[j] < x:
				x = g[j]
		if c > 0:
			print(c)
		else:
			print('UNFIT')


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().strip().split()))
	m = 0
	pmin = l[0]
	for i in range(n):
		if pmin < l[i]:
			m = max(m, l[i] - pmin)
		else:
			pmin = l[i]
	if m == 0:
		print('UNFIT')
	else:
		print(m)
	t -= 1


for te in range(int(input())):
	z = int(input())
	k = []
	l = list(map(int, input().split(' ')))
	mini = max(l) + 1
	for i in range(0, z):
		mini = min(mini, l[i])
		k.append(l[i] - mini)
	if max(k) <= 0:
		print('UNFIT')
	else:
		print(max(k))


t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	suf = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suf[i] = lis[i]
		else:
			suf[i] = max(lis[i], suf[i + 1])
	ans = 0
	for i in range(n - 1):
		if suf[i + 1] > lis[i]:
			ans = max(suf[i + 1] - lis[i], ans)
	if ans == 0:
		print('UNFIT')
	else:
		print(ans)


inp = input()
num_cases = int(inp)
for i in range(num_cases):
	inp = input()
	n = int(inp)
	inp = input()
	inp = inp.split(' ')
	listInt = list(map(int, inp))
	minlist = list()
	maxlist = list()
	temp = listInt[0]
	minlist.append(temp)
	for j in range(1, n):
		if listInt[j] < temp:
			minlist.append(listInt[j])
			temp = listInt[j]
		else:
			minlist.append(temp)
	temp = listInt[n - 1]
	maxlist.append(temp)
	for j in range(n - 2, -1, -1):
		if listInt[j] > temp:
			maxlist.append(listInt[j])
			temp = listInt[j]
		else:
			maxlist.append(temp)
	temp = 0
	for j in range(n):
		if maxlist[j] - minlist[n - j - 1] > temp:
			temp = maxlist[j] - minlist[n - j - 1]
	if temp is 0:
		print('UNFIT')
	else:
		print(temp)


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	G = get_mint()
	max_goal = 0
	least_goal = G[0]
	for gi in G[1:]:
		if gi - least_goal > max_goal:
			max_goal = gi - least_goal
		if gi < least_goal:
			least_goal = gi
	if max_goal > 0:
		print(max_goal)
	else:
		print('UNFIT')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	c = 0
	if n == 1:
		print('UNFIT')
	else:
		for j in range(1, n):
			if arr[j] - x > c:
				c = arr[j] - x
			if arr[j] < x:
				x = arr[j]
		if c > 0:
			print(c)
		else:
			print('UNFIT')


t = int(input())
for q in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	minn = l[0]
	ans = 0
	for i in range(n):
		if minn < l[i]:
			ans = max(ans, l[i] - minn)
		else:
			minn = l[i]
	if ans <= 0:
		print('UNFIT')
	else:
		print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	goals = list(map(int, input().split()))
	min_goals = goals[0]
	max_diff = -1
	for i in range(1, N):
		if goals[i] > min_goals:
			max_diff = max(max_diff, goals[i] - min_goals)
		else:
			min_goals = goals[i]
	if max_diff == -1:
		print('UNFIT')
	else:
		print(max_diff)


t = int(input())
while t:
	t -= 1
	n = int(input())
	li = list(map(int, input().split()))
	(mini, maxi) = (li[0], li[0])
	res = 0
	for i in range(1, n):
		maxi = max(maxi, li[i])
		if mini > li[i]:
			mini = li[i]
			maxi = 0
		res = max(res, maxi - mini)
	if res == 0:
		print('UNFIT')
	else:
		print(res)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	s = l[0]
	d = 0
	for i in range(1, n):
		if l[i] < l[i - 1]:
			s = min(s, l[i])
		else:
			d = max(d, l[i] - s)
	print(d) if d != 0 else print('UNFIT')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	fst_game = li.pop(0)
	max_diff = 0
	for i in li:
		if i >= fst_game and max_diff < i - fst_game:
			max_diff = i - fst_game
		elif i < fst_game:
			fst_game = i
	if max_diff > 0:
		print(max_diff)
	else:
		print('UNFIT')


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	p = a[0]
	s = 0
	for i in range(n):
		if p < a[i]:
			s = max(s, a[i] - p)
		else:
			p = a[i]
	if s == 0:
		print('UNFIT')
	else:
		print(s)


testCases = int(input())
results = []
for case in range(testCases):
	n = int(input())
	goals = input().split(' ')
	for index in range(len(goals)):
		goals[index] = int(goals[index])
	maxScore = 0
	minGoal = goals[0]
	for i in range(1, len(goals)):
		if i == 1:
			maxScore = max(goals[1] - minGoal, maxScore)
		else:
			maxScore = max(goals[i] - minGoal, maxScore)
		minGoal = min(minGoal, goals[i])
	results.append(maxScore)
for r in results:
	if r == 0:
		print('UNFIT')
	else:
		print(r)


n = int(input())
for _ in range(n):
	v = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print('UNFIT')
	else:
		t = l[0]
		k = -10 ** 10
		for i in range(1, v):
			k = max(k, l[i] - t)
			t = min(t, l[i])
		if k < 1:
			print('UNFIT')
		else:
			print(k)


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	a = list(map(int, input().split()))
	maxi = 0
	mini = a[0]
	for i in a:
		maxi = max(maxi, i - mini)
		mini = min(mini, i)
	if maxi <= 0:
		print('UNFIT')
	else:
		print(maxi)


t = int(input())
for i in range(t):
	num = int(input())
	arr = list(map(int, input().split()))
	count = 0
	list1 = []
	x = arr[0]
	for i in range(num - 1):
		if arr[i] < arr[i + 1]:
			count = count + 1
			x = min(arr[i], x)
			list1.append(arr[i + 1] - x)
	if count >= 1:
		print(max(list1))
	else:
		print('UNFIT')


def fun(arr):
	if len(arr) <= 1:
		return 'UNFIT'
	diff = float('-inf')
	minn = arr[0]
	for i in range(1, len(arr)):
		if arr[i] < minn:
			minn = arr[i]
		elif arr[i] > minn:
			diff = max(diff, arr[i] - minn)
	if diff == float('-inf'):
		return 'UNFIT'
	return diff
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(fun(arr))


t = int(input())
while t:
	t -= 1
	n = int(input())
	ls = list(map(int, input().split()))
	(nmax, nmin) = (0, 0)
	ans = -1000000000.0
	for i in range(n):
		if ls[i] <= ls[nmin]:
			ans = max(ans, ls[nmax] - ls[nmin])
			nmin = i
			nmax = nmin
		elif ls[nmax] <= ls[i]:
			nmax = i
			ans = max(ans, ls[nmax] - ls[nmin])
	if ans <= 0:
		print('UNFIT')
	else:
		print(ans)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	maxDiff = 0
	pre = L[0]
	for i in range(1, len(L)):
		diff = L[i] - pre
		if diff > 0:
			if diff > maxDiff:
				maxDiff = diff
		else:
			pre = L[i]
	print('UNFIT' if maxDiff == 0 else maxDiff)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mini = l[0]
	l.pop(0)
	ans = 0
	for i in l:
		if i > mini:
			ans = max(ans, i - mini)
		else:
			mini = i
	if ans > 0:
		print(ans)
	else:
		print('UNFIT')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	minV = l[0]
	ans = -1
	for i in l:
		ans = max(ans, i - minV)
		minV = min(minV, i)
	if ans <= 0:
		print('UNFIT')
		continue
	print(ans)


def maxdis(l):
	n = len(l)
	mn = 999999999999
	(diff, mxdiff) = (0, 0)
	for i in range(n):
		if l[i] < mn:
			mn = l[i]
		else:
			diff = l[i] - mn
			if mxdiff < diff:
				mxdiff = diff
	return mxdiff
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dis = maxdis(l)
	print(dis if dis > 0 else 'UNFIT')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = -1000000000.0
	minn = l[0]
	for i in range(1, n):
		if minn >= l[i]:
			minn = l[i]
		else:
			ans = max(ans, l[i] - minn)
	if ans >= 1:
		print(ans)
	else:
		print('UNFIT')


from sys import stdin, stdout
from heapq import heappush, heappop
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	n = stdint()
	nums = seq()
	heap = []
	nger = []
	for i in range(n - 1, -1, -1):
		if heap and nums[i] < -heap[0]:
			nger.append(-heap[0] - nums[i])
		else:
			nger.append(-1)
		heappush(heap, -nums[i])
	maxVal = max(nger)
	if maxVal == -1:
		print('UNFIT')
	else:
		print(maxVal)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('UNFIT')
	else:
		x = 0
		m = a[0]
		for i in range(n):
			if a[i] > m:
				x = max(x, a[i] - m)
			else:
				m = a[i]
		if x == 0:
			print('UNFIT')
		else:
			print(x)


t = int(input())
for i in range(t):
	n = int(input())
	li = [int(x) for x in input().split(' ')]
	s = 0
	a = li[0]
	for i in range(0, n):
		if a < li[i]:
			s = max(s, li[i] - a)
		else:
			a = li[i]
	if s == 0:
		print('UNFIT')
	else:
		print(s)


def goals(arr):
	x = [] + arr
	x.sort(reverse=True)
	if arr == x:
		return 'UNFIT'
	table = [0 for i in range(len(arr))]
	minpos = 0
	maxval = 0
	for i in range(minpos + 1, len(arr)):
		if arr[i] < arr[minpos]:
			minpos = i
		elif arr[i] - arr[minpos] > maxval:
			maxval = arr[i] - arr[minpos]
	return maxval
t = int(input())
for i in range(t):
	x = int(input())
	arr = [int(i) for i in input().split()]
	print(goals(arr))


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	m = A[0]
	count = 0
	for j in range(1, n):
		if A[j] - m > count:
			count = A[j] - m
		if A[j] < m:
			m = A[j]
	if count > 0:
		print(count)
	else:
		print('UNFIT')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	cmin = A[0]
	ans = 0
	if N == 1:
		print('UNFIT')
		continue
	for i in range(1, N):
		x = A[i]
		if x < cmin:
			cmin = x
		else:
			ans = max(ans, x - cmin)
	if ans:
		print(ans)
	else:
		print('UNFIT')


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	small = x[0]
	mx = -5
	for i in range(n - 1):
		if x[i + 1] < x[i]:
			small = min(x[i + 1], small)
		else:
			mx = max(mx, x[i + 1] - small)
	if mx < 1:
		print('UNFIT')
	else:
		print(mx)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = a[0]
	goal = 0
	if n == 1:
		print('UNFIT')
	else:
		for i in range(1, n):
			if a[i] - p > goal:
				goal = a[i] - p
			if a[i] < p:
				p = a[i]
		if goal > 0:
			print(goal)
		else:
			print('UNFIT')


for _ in range(int(input())):
	N = int(input())
	lst = list(map(int, input().split(' ')))
	f = 0
	m = lst[0]
	for i in range(len(lst)):
		if lst[i] - m > f:
			f = lst[i] - m
		if lst[i] < m:
			m = lst[i]
	if f >= 1:
		print(f)
	else:
		print('UNFIT')


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	p = l[0]
	c = 0
	if n == 1:
		print('UNFIT')
	else:
		for j in range(1, n):
			if l[j] - p > c:
				c = l[j] - p
			if l[j] < p:
				p = l[j]
		if c < 1:
			print('UNFIT')
		else:
			print(c)


def max_diff(n, arr):
	if n == 1:
		return 'UNFIT'
	min_element = arr[0]
	max_diff = arr[1] - arr[0]
	for i in range(1, n):
		if arr[i] - min_element > max_diff:
			max_diff = arr[i] - min_element
		if arr[i] < min_element:
			min_element = arr[i]
	if max_diff > 0:
		return max_diff
	return 'UNFIT'
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(max_diff(n, arr))


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	maxdiff = 0
	maxgoal = [arr[-1]] * n
	for i in range(n - 2, -1, -1):
		maxgoal[i] = max(arr[i], maxgoal[i + 1])
		maxdiff = max(maxdiff, maxgoal[i] - arr[i])
	print(maxdiff if maxdiff else 'UNFIT')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxdiff = 0
	min1 = a[0]
	for j in range(n):
		if a[j] > min1:
			maxdiff = max(maxdiff, a[j] - min1)
		else:
			min1 = a[j]
	if maxdiff == 0:
		print('UNFIT')
	else:
		print(maxdiff)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	smin = a[0]
	for i in range(n):
		if a[i] > smin:
			c = max(c, a[i] - smin)
		else:
			smin = a[i]
	if c == 0:
		print('UNFIT')
	else:
		print(c)