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

Finally, progress reached the Madoka family and she decided to play with her little sister in the sensational game Space Arrays.

The rules of the game are as follows:
Initially, a sequence $a_{1}, a_{2}, \ldots, a_{N}$ is given.
The players alternate turns.
In each turn, the current player must choose an index $i$ and increment $a_{i}$, i.e. change $a_{i}$ to $a_{i} + 1$.
Afterwards, if there is no permutation $p_{1}, p_{2}, \ldots, p_{N}$ of the integers $1$ through $N$ such that $a_{i} ≤ p_{i}$ holds for each valid $i$, the current player loses.
Otherwise, the game continues with the next turn.

Madoka is asking you to help her ― tell her if the first player (the player that plays in the first turn) or second player wins this game if both play optimally.

------  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 the string "First" if the first player wins or "Second" if the second player wins (without quotes).

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
The sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$
$1 ≤ a_{i} ≤ N$ for each valid $i$

------  Subtasks ------
Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
4

4

1 2 3 3

4

1 1 3 3

5

1 2 2 1 5

3

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

Second

Second

Second
----- explanation 1 ------ 
Example case 1: 
- If the first player increases the fourth element,  the resulting sequence is $(1,2,3,4)$. The second player loses after increasing any of the elements.
- If the first player increases the second element, the resulting sequence is $(1,3,3,3)$, and he loses because there is no valid permutation. For example if $p=(2,1,4,3)$,  the second element of $a$ is greater than the second element of $p$.

Source: codechef | Difficulty: MEDIUM
Tags: Data structures

Game theory


Solutions:
for _ in range(int(input())):
	N = int(input())
	arr = sorted(map(int, input().split()))
	k = 0
	for i in range(len(arr)):
		if i + 1 - arr[i] < 0:
			print('Second')
			break
		k += i + 1 - arr[i]
	else:
		print('First' if k % 2 else 'Second')


t = int(input())
for kkk in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	first = 1
	second = 0
	win = 'Second'
	if a[0] > 1:
		if first == 1:
			win = 'Second'
		else:
			win = 'First'
		print(win)
		continue
	for i in range(1, n):
		if a[i] > i + 1:
			win = 'Second'
			break
		if a[i - 1] >= a[i]:
			if second == 1:
				if (a[i - 1] + 1 - a[i]) % 2 == 1:
					win = 'Second'
					second = 0
					first = 1
				else:
					win = 'First'
					second = 1
					first = 0
			elif (a[i - 1] + 1 - a[i]) % 2 == 1:
				win = 'First'
				second = 1
				first = 0
			else:
				win = 'Second'
				second = 0
				first = 1
			a[i] = a[i - 1] + 1
	print(win)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	cnt = 0
	for i in range(len(nums)):
		if i + 1 < nums[i]:
			cnt = 0
			break
		else:
			cnt += i + 1 - nums[i]
	if cnt % 2 == 0:
		print('Second')
	else:
		print('First')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	flag = False
	sum = 0
	for i in a[::-1]:
		t = n - i
		if t < 0:
			flag = True
			break
		else:
			sum += t
		n -= 1
	if flag:
		print('Second')
	elif sum % 2 == 0:
		print('Second')
	else:
		print('First')


def Solve(l, n):
	l.sort()
	count = 0
	for i in range(n):
		if l[i] > i + 1:
			return 'Second'
		count = count + l[i] - i + 1
	if count % 2 != 0:
		return 'First'
	return 'Second'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(Solve(l, n))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	f = 0
	for i in range(n):
		if i + 1 < arr[i]:
			f = 1
			break
		ans += i + 1 - arr[i]
	if f == 1:
		print('Second')
	elif ans % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	a.sort()
	for i in range(n):
		if i + 1 - a[i] < 0:
			c = 0
			break
		c += i + 1 - a[i]
	if c % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	(count, flag) = (0, 0)
	list1 = [int(x) for x in input().split()]
	list1.sort()
	for i in range(n):
		if list1[i] <= i + 1:
			count += i + 1 - list1[i]
		else:
			flag = 1
			break
	if count % 2 == 0 or flag == 1:
		print('Second')
	else:
		print('First')


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	temp = 0
	list1 = sorted(list(map(int, input().split())))
	for i in range(n):
		if list1[i] > i + 1:
			count = 0
			break
		else:
			count = count + (i + 1 - list1[i])
	if count % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	k = n * (n + 1) // 2
	l = sorted(list(map(int, input().split())))
	s = sum(l)
	f = False
	for i in range(n):
		if l[i] > i + 1:
			print('Second')
			f = True
			break
	if not f:
		if (k - s) % 2 == 1:
			print('First')
		else:
			print('Second')


t = int(input())
for j in range(t):
	n = int(input())
	L = [int(i) for i in input().split()]
	L.sort()
	c = 0
	L1 = [i for i in range(1, n + 1)]
	for i in range(n):
		if L[i] > L1[i]:
			c = 0
			break
		else:
			c += L1[i] - L[i]
	if c % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	i = int(input())
	j = sorted(list(map(int, input().split())))
	diff = 0
	for val in range(1, i + 1):
		if val - j[val - 1] >= 0:
			diff += val - j[val - 1]
		else:
			diff = 2
			break
	if diff % 2 == 1:
		print('First')
	else:
		print('Second')


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ops = 0
	flag = True
	for i in range(n):
		if arr[i] > i + 1:
			flag = False
			break
		ops += i + 1 - arr[i]
	if not flag or ops & 1 == 0:
		print('Second')
	else:
		print('First')


T = int(input())
for x in range(T):
	n = int(input())
	a = sorted(map(int, input().split()))
	c = 0
	i = 1
	for x in a:
		if x > i:
			print('Second')
			break
		c += i - x
		i += 1
	else:
		print('First' if c % 2 else 'Second')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	flag = 0
	result = 0
	for i in range(n):
		if i + 1 - arr[i] < 0:
			flag = 1
			break
		else:
			result += i + 1 - arr[i]
	if result % 2 == 0 or flag == 1:
		print('Second')
	else:
		print('First')


class sol:

	def ans(self, n, a):
		b = list(a)
		b.sort()
		c = list(range(1, n + 1))
		if c == b:
			return 'Second'
		else:
			s = 0
			for i in c:
				k = b.pop(0)
				if k != i:
					if k - i > 0:
						return 'Second'
					else:
						s += i - k
			if s % 2 == 0:
				return 'Second'
			return 'First'
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sol()
	print(b.ans(n, a))


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	w = 0
	a.sort()
	for i in range(n):
		if a[i] <= i + 1:
			w += abs(a[i] - (i + 1))
		else:
			w = 0
			break
	if w % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	l = sorted([int(i) for i in input().split()])
	a = [int(i) for i in range(1, n + 1)]
	x = 0
	ans = ['Second', 'First']
	done = 0
	for ind in range(n):
		if l[ind] > a[ind]:
			print(ans[0])
			done = 1
			break
		else:
			x += a[ind] - l[ind]
	if not done:
		print(ans[x % 2])


def solve(arr):
	arr = sorted(arr)
	d = 0
	for i in range(n):
		if arr[i] > i + 1:
			print('Second')
			return
		d += max(0, i + 1 - arr[i])
	if d % 2 == 0:
		print('Second')
	else:
		print('First')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr)


for satya in range(int(input())):
	sai = int(input())
	dad = sai * (sai + 1) // 2
	mad = sorted(list(map(int, input().split())))
	don = sum(mad)
	flag = False
	for i in range(sai):
		if mad[i] > i + 1:
			print('Second')
			flag = True
			break
	if not flag:
		if (dad - don) % 2 == 1:
			print('First')
		else:
			print('Second')


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	flag = 1
	c = 0
	for i in range(n):
		temp = i + 1 - L[i]
		if temp < 0:
			flag = 0
			break
		if temp > 0:
			c += temp
	if flag == 0 or c % 2 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(0, n):
		if a[i] > i + 1:
			print('Second')
			break
	else:
		s = sum((i - j for (i, j) in zip(a, range(1, n + 1))))
		print('First' if s % 2 != 0 else 'Second')


t = int(input())
for j in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	k = sorted(b)
	c = 1
	flg = 0
	count = 0
	for i in range(n):
		if k[i] <= c:
			count = count + abs(k[i] - c)
		else:
			print('Second')
			flg = 1
			break
		c = c + 1
	if flg == 0:
		if count % 2 == 0:
			print('Second')
		else:
			print('First')


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	incorrect_array = False
	arr_num = [0] * length
	for j in arr:
		arr_num[j - 1] += 1
	add = 0
	total = 0
	expected = 0
	for j in range(length - 1, -1, -1):
		add += arr_num[j]
		if add > length - j:
			incorrect_array = True
			break
		total += arr_num[j] * (j + 1)
		expected += j + 1
	moves = expected - total
	if incorrect_array:
		print('Second')
	elif moves & 1:
		print('First')
	else:
		print('Second')


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	incorrect_array = False
	arr.sort()
	moves = 0
	for j in range(length):
		if arr[j] > j + 1:
			incorrect_array = True
			break
		else:
			moves += j + 1 - arr[j]
	if incorrect_array:
		print('Second')
	elif moves & 1:
		print('First')
	else:
		print('Second')


from sys import stdin
ip = stdin.readline
from collections import Counter
for _ in range(int(ip())):
	n = int(ip())
	ar = list(map(int, ip().split()))
	ar.sort()
	ans = 0
	res = ''
	for i in range(0, n):
		if ar[i] > i + 1:
			res = 'Second'
			break
		else:
			ans += i + 1 - ar[i]
	if res != '':
		print(res)
	else:
		res = 'Second' if ans % 2 == 0 else 'First'
		print(res)


t = int(input())
while t:
	t -= 1
	x = int(input())
	ls = list(map(int, input().split()))
	ls.sort()
	bl = True
	count = 0
	for i in range(len(ls)):
		if ls[i] > i + 1:
			bl = False
			break
		else:
			count += i + 1 - ls[i]
	if bl == False:
		print('Second')
	elif count % 2 == 0:
		print('Second')
	else:
		print('First')


t = int(input())
for _ in range(t):
	x = int(input())
	arr = list(map(int, input().split()))
	total_sum = 0
	flag = 0
	arr.sort()
	for i in range(len(arr)):
		if arr[i] <= i + 1:
			total_sum += i + 1 - arr[i]
		else:
			flag = 1
			print('Second')
			break
	if flag == 0:
		if total_sum % 2 == 0:
			print('Second')
		else:
			print('First')


for i in [*open(0)][2::2]:
	ar = sorted([*map(int, i.split())])
	k = 0
	l = 1
	for j in range(len(ar)):
		if ar[j] > l:
			break
		else:
			k += l - ar[j]
			l += 1
	if l - 1 != len(ar):
		print('Second')
	else:
		print('First' if k & 1 else 'Second')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	sum = 0
	for i in range(n):
		temp = i + 1 - l[i]
		if temp < 0:
			sum = -1
			break
		else:
			sum += temp
	if sum < 0 or sum % 2 == 0:
		print('Second')
	else:
		print('First')


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	count = 0
	for i in range(n):
		if x[i] > i + 1:
			count = 1
			break
	g = sum(x) - n * (n + 1) // 2
	if count == 1 or g % 2 == 0:
		print('Second')
	else:
		print('First')


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	j = 1
	sum = 0
	for i in l:
		if i <= j:
			sum += j - i
		else:
			sum = 0
			break
		j += 1
	if sum % 2 == 0:
		print('Second')
	else:
		print('First')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	f = False
	E = 0
	for i in range(n):
		if arr[i] > i + 1:
			f = True
			break
		else:
			E += i + 1 - arr[i]
	if f or E == 0:
		print('Second')
	elif E % 2 == 1:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	a.sort()
	flag = False
	e = 0
	for i in range(N):
		if a[i] > i + 1:
			flag = True
			break
		else:
			e += i + 1 - a[i]
	if flag or e == 0:
		print('Second')
	elif e % 2 == 1:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	n = int(input())
	space = list(map(int, input().split()))
	space.sort()
	sume = 0
	ans = 'First'
	for i in range(n):
		if space[i] > i + 1:
			ans = 'Second'
			break
		sume += i + 1 - space[i]
	else:
		if sume & 1 == 0:
			ans = 'Second'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	count = [0] * n
	for i in a:
		count[i - 1] += 1
	for i in range(1, n):
		count[i] += count[i - 1]
	ans = False
	for i in range(n):
		if count[i] < i + 1:
			ans = True
			break
	if ans:
		print('Second')
	else:
		s = n * (n + 1) // 2
		s = sum(a) - s
		if s % 2 == 0 or 1 not in a or a.count(n) > 1:
			print('Second')
		else:
			print('First')


for _ in range(int(input())):
	n = int(input())
	a = sorted([int(x) for x in input().split()])
	ans = False
	for (i, e) in enumerate(a):
		if e > i + 1:
			ans = True
			break
	if ans:
		print('Second')
	else:
		s = n * (n + 1) // 2
		s = sum(a) - s
		if s % 2 == 0:
			print('Second')
		else:
			print('First')


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	r = 0
	for i in range(n):
		d = i + 1 - a[i]
		if d < 0:
			r = 1
		else:
			s += d
	if r == 1:
		print('Second')
	elif s % 2 == 0:
		print('Second')
	else:
		print('First')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	l.sort()
	lasti = 0
	for i in range(n):
		if l[i] <= i + 1:
			c += i + 1 - l[i]
			lasti = i
		else:
			break
	if lasti < n - 1 or c % 2 == 0:
		print('Second')
	else:
		print('First')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	a.sort()
	f = 0
	for i in range(n):
		if a[i] > i + 1:
			f = 1
			break
		else:
			count += a[i] - (i + 1)
	if f or count & 1 == 0:
		print('Second')
	else:
		print('First')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = 0
	arr.sort()
	last1 = 0
	for i in range(n):
		if arr[i] <= i + 1:
			s = s + (i + 1 - arr[i])
			lasti = i
		else:
			break
	if lasti < n - 1 or s % 2 == 0:
		ans = 'Second'
	else:
		ans = 'First'
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	s = 0
	li = 0
	for i in range(n):
		if l[i] <= i + 1:
			s = s + (i + 1 - l[i])
			li = i
		else:
			break
	if s % 2 == 0 or li < n - 1:
		print('Second')
	else:
		print('First')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	flag = 0
	for i in range(n):
		if i + 1 >= a[i]:
			c += i + 1 - a[i]
		else:
			flag = 1
			break
	if c % 2 == 0 or flag:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	sum1 = 0
	flag = True
	for j in range(len(x)):
		if j + 1 - x[j] >= 0:
			sum1 += j + 1 - x[j]
		else:
			flag = False
	if sum1 % 2 == 0 or flag == False:
		print('Second')
	else:
		print('First')