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!)

-----Example:-----Input:

3

6

3 7 1 4 2 4

5

5 4 3 2 1

5

4 3 2 2 3

Output:

4

UNFIT

1

Explanation:

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: interview

Starter code:

Solutions:
T = int(input())
for j in range(0,T):
 line1, line2 = input(), input()
 seq = line2.split()
 current_min = 1000001
 current_max = 0
 max_spread = 0
 for i in range(0,len(seq)):
  current_value = int(seq[i])
  if current_min > current_value:
   current_min = current_value
   current_max = current_value
  elif current_max < current_value:
   current_max = current_value
   if max_spread < (current_max - current_min):
    max_spread = current_max - current_min 
 if max_spread > 0:
  print(max_spread)
 else:
  print("UNFIT")

import sys

def main():
 t=int(input())
 while(t>0):
  size=input()
  n=input().split()
  nmin = int(n[0])
  ndiff =0
  for i in range(1,len(n)):
   k=int(n[i])
   if k < nmin:
    nmin = k
   else:
    if (k-nmin) > ndiff:
     ndiff = k-nmin
  if ndiff > 0:
   print(ndiff)
  else:
   print("UNFIT")
  t-=1


def __starting_point():
 main()
 return
__starting_point()

tc = int(input()) 

from sys import stdin

lines = stdin.readlines()
out = ""
i = 0
for line in lines:
 if i % 2 == 0:
  i += 1
  continue

  
 nn = list(map (int, line.split()))
 greatest = 0
 least = nn[0]
 diff = 0
 for n in nn:
  if n > least and n - least > diff:
   diff = n - least;
  elif n < least:
   least = n
   
 if diff > 0:
  out+=str(diff) + "\n"
 else:
  out += "UNFIT\n"
 i += 1
print(out)

#!/usr/bin/env python

def process(t, N, G):
 Improvment = 0
 CurrentMin = G[0]
 CurrentMax = G[0]
 for n in range(1, N):
  if CurrentMax < G[n]:
   CurrentMax = G[n]
   Improvment = max(Improvment, CurrentMax-CurrentMin)
  elif CurrentMin > G[n]:
    CurrentMin = G[n]
    CurrentMax = G[n]
 return Improvment or 'UNFIT'

def main():
 T = int(input())
 for t in range(T):
  N = int(input())
  G = list(map(int, input().strip().split()[:N]))
  if len(G) != N: print(1 / 0)
  print(process(t, N, G))

main()



#!/usr/bin/env python

def process(t, N, G):
 Improvment = 0
 CurrentMin = G[0]
 CurrentMax = G[0]
 for n in range(1, N):
  if CurrentMax < G[n]:
   CurrentMax = G[n]
   Improvment = max(Improvment, CurrentMax-CurrentMin)
  elif CurrentMin > G[n]:
    CurrentMin = G[n]
    CurrentMax = G[n]
 return Improvment or 'UNFIT'

def main():
 T = int(input())
 for t in range(T):
  N = int(input())
  G = list(map(int, input().strip().split()[:N]))
  print(process(t, N, G))

main()