Two players are playing a game. They have a permutation of integers $1$, $2$, ..., $n$ (a permutation is an array where each element from $1$ to $n$ occurs exactly once). The permutation is not sorted in either ascending or descending order (i. e. the permutation does not have the form $[1, 2, \dots, n]$ or $[n, n-1, \dots, 1]$).

Initially, all elements of the permutation are colored red. The players take turns. On their turn, the player can do one of three actions:

rearrange the elements of the permutation in such a way that all red elements keep their positions (note that blue elements can be swapped with each other, but it's not obligatory);

change the color of one red element to blue;

skip the turn.

The first player wins if the permutation is sorted in ascending order (i. e. it becomes $[1, 2, \dots, n]$). The second player wins if the permutation is sorted in descending order (i. e. it becomes $[n, n-1, \dots, 1]$). If the game lasts for $100^{500}$ turns and nobody wins, it ends in a draw.

Your task is to determine the result of the game if both players play optimally.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3 \le n \le 5 \cdot 10^5$) — the size of the permutation.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ — the permutation itself. The permutation $p$ is not sorted in either ascending or descending order.

The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.


-----Output-----

For each test case, print First if the first player wins, Second if the second player wins, and Tie if the result is a draw.


-----Examples-----

Input
4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4
Output
First
Tie
Second
Tie


-----Note-----

Let's show how the first player wins in the first example.

They should color the elements $3$ and $4$ blue during their first two turns, and then they can reorder the blue elements in such a way that the permutation becomes $[1, 2, 3, 4]$. The second player can neither interfere with this strategy nor win faster.

Difficulty: MEDIUM_HARD
Tags: Game theory

Starter code:

Solutions:
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	s = 0
	for j in range(n):
		if a[j] == j + 1:
			f += 1
		if a[j] == n - j:
			if n % 2 == 0 or j != (n - 1) // 2:
				s += 1
	if f >= (n + 1) // 2:
		print('First')
	elif s >= (n + 2) // 2:
		print('Second')
	else:
		print('Tie')


import sys
input = sys.stdin.readline

def solve(L):
	a = 0
	b = 0
	k = 0
	for i in range(len(L)):
		if L[i] != i + 1:
			a += 1
		if L[i] != len(L) - i:
			b += 1
		if L[i] not in [i + 1, len(L) - i]:
			k += 1
	if b - a >= k:
		return 'First'
	if b + 1 + k <= a:
		return 'Second'
	return 'Tie'
for i in ' ' * int(input()):
	n = int(input())
	print(solve(list(map(int, input().split()))))


import sys
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import product, combinations, permutations
from math import sin, cos
ipt = sys.stdin.readline
iin = lambda : int(ipt())
lmin = lambda : list(map(int, ipt().split()))
for _ in range(iin()):
	N = iin()
	P = lmin()
	f = 0
	s = 0
	for i in range(N):
		f += P[i] == i + 1
		s += P[N - i - 1] == i + 1
	if N % 2:
		if P[N // 2] == N // 2 + 1:
			N -= 1
			f -= 1
			s -= 1
			if f >= N // 2:
				print('First')
			elif s > N // 2:
				print('Second')
			else:
				print('Tie')
		elif f > N // 2:
			print('First')
		elif s > N // 2:
			print('Second')
		else:
			print('Tie')
	elif f >= N // 2:
		print('First')
	elif s > N // 2:
		print('Second')
	else:
		print('Tie')


import sys
lst = []
time = 0
n = 0
for line in sys.stdin:
	if time == 0:
		time = 1
		n = int(line.split()[0])
		continue
	lst.append([int(x) for x in line.split()])
for i in range(n):
	l = lst[2 * i][0]
	c11 = 0
	c21 = 0
	c12 = 0
	c22 = 0
	for j in range(l):
		b1 = lst[2 * i + 1][j] != j + 1
		b2 = lst[2 * i + 1][j] != l - j
		if b1:
			c11 += 1
		if b2:
			c21 += 1
		if b1 == True and b2 == False:
			c12 += 1
		if b2 == True and b1 == False:
			c22 += 1
	if c11 <= c22:
		print('First')
	elif c21 <= c12 - 1:
		print('Second')
	else:
		print('Tie')


t = int(input())
for i in range(t):
	le = int(input())
	l = [int(i) for i in input().split()]
	start = 1
	end = le
	fi = 0
	se = 0
	shared = 0
	for i in l:
		if i == start:
			fi += 1
		elif i == end:
			se += 1
		else:
			shared += 1
		start += 1
		end -= 1
	if fi >= le - fi:
		print('First')
	elif se > le - se:
		print('Second')
	else:
		print('Tie')


t = int(input())
results = []
for i in range(t):
	n = int(input())
	nums = list(map(int, input().strip().split()))
	ascending = []
	for j in range(1, n + 1):
		ascending.append(j)
	descending = []
	for j in range(n, 0, -1):
		descending.append(j)
	asc_diff = set()
	for j in range(n):
		if ascending[j] != nums[j]:
			asc_diff.add(ascending[j])
	desc_diff = set()
	for j in range(n):
		if descending[j] != nums[j]:
			desc_diff.add(descending[j])
	intersect = asc_diff & desc_diff
	in_a_not_b = asc_diff - desc_diff
	in_b_not_a = desc_diff - asc_diff
	if abs(len(in_a_not_b) - len(in_b_not_a)) < len(intersect):
		results.append('Tie')
	elif len(in_b_not_a) - len(in_a_not_b) == len(intersect):
		results.append('First')
	elif len(in_a_not_b) - len(in_b_not_a) == len(intersect):
		results.append('Tie')
	elif len(in_a_not_b) - len(in_b_not_a) > len(intersect):
		results.append('Second')
	elif len(in_b_not_a) - len(in_a_not_b) > len(intersect):
		results.append('First')
for i in results:
	print(i)


num_case = int(input())
for case_idx in range(num_case):
	n = int(input())
	p = list(map(int, input().split()))
	first_unique = second_unique = common = 0
	for i in range(n):
		if p[i] != i + 1 and p[i] != n - i:
			common += 1
		elif p[i] != i + 1:
			first_unique += 1
		elif p[i] != n - i:
			second_unique += 1
	if first_unique + common <= second_unique:
		print('First')
	elif second_unique + common < first_unique:
		print('Second')
	else:
		print('Tie')


for tc in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	(a, b, c) = (0, 0, 0)
	for i in range(n):
		if p[i] != i + 1 and p[i] != n - i:
			c += 1
		elif p[i] != i + 1:
			a += 1
		elif p[i] != n - i:
			b += 1
	if a + c <= b:
		print('First')
	elif b + c < a:
		print('Second')
	else:
		print('Tie')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(f, s, c) = (0, 0, 0)
	for i in range(n):
		if a[i] != i + 1 and a[i] != n - i:
			c += 1
		elif a[i] != i + 1:
			f += 1
		elif a[i] != n - i:
			s += 1
	if f + c <= s:
		print('First')
	elif s + c < f:
		print('Second')
	else:
		print('Tie')


for test in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().rstrip().split()]
	a = 0
	b = 0
	c = 0
	for i in range(0, n):
		if arr[i] != i + 1 and arr[i] != n - i:
			c += 1
		elif arr[i] != i + 1:
			a += 1
		elif arr[i] != n - i:
			b += 1
	if a + c <= b:
		print('First')
	elif b + c < a:
		print('Second')
	else:
		print('Tie')


def winner(arr, n):
	f = 0
	s = 0
	c = 0
	for i in range(n):
		if arr[i] == i + 1 and arr[i] != n - i:
			f += 1
		elif arr[i] != i + 1 and arr[i] == n - i:
			s += 1
		elif arr[i] != n - i and arr[i] != i + 1:
			c += 1
	if s + c <= f:
		return 'First'
	elif f + c < s:
		return 'Second'
	else:
		return 'Tie'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	print(winner(l, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = 0
	a2 = 0
	ob = 0
	for i in range(n):
		if a[i] != i + 1 and a[i] != n - i:
			ob += 1
		elif a[i] != i + 1:
			a1 += 1
		elif a[i] != n - i:
			a2 += 1
	if a2 + ob < a1:
		print('Second')
	elif a1 + ob <= a2:
		print('First')
	else:
		print('Tie')


import math
t = int(input())
while t > 0:
	n = int(input())
	L = list(map(int, input().split()))
	l = 1
	r = n
	l_count = 0
	r_count = 0
	all_count = 0
	for i in L:
		l_count += i != l
		r_count += i != r
		all_count += i != l and i != r
		l += 1
		r -= 1
	l_count -= all_count
	r_count -= all_count
	if l_count + all_count <= r_count:
		print('First')
	elif r_count + all_count < l_count:
		print('Second')
	else:
		print('Tie')
	t -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	frst = 0
	scnd = 0
	both = 0
	for i in range(1, n + 1):
		if arr[i - 1] != i and arr[i - 1] != n - i + 1:
			both += 1
		elif arr[i - 1] != n - i + 1:
			scnd += 1
		elif arr[i - 1] != i:
			frst += 1
	if frst + both <= scnd:
		print('First')
	elif scnd + both < frst:
		print('Second')
	else:
		print('Tie')


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	fir = sec = 0
	mid = 0
	for i in range(1, n + 1):
		if nums[i - 1] != i and nums[i - 1] != n - i + 1:
			mid += 1
		elif nums[i - 1] != n - i + 1:
			sec += 1
		elif nums[i - 1] != i:
			fir += 1
	if fir + mid <= sec:
		print('First')
	elif sec + mid < fir:
		print('Second')
	else:
		print('Tie')


for t in range(int(input())):
	n = int(input())
	p = [int(x) for x in input().split()]
	(u1, u2, ucommon) = (0, 0, 0)
	for (i, e) in enumerate(p):
		(a, b) = (e != i + 1, e != n - i)
		if a and b:
			ucommon += 1
		if a:
			u1 += 1
		if b:
			u2 += 1
	(s1, s2) = (n - u1, n - u2)
	if u2 - ucommon >= u1:
		print('First')
	elif u1 - ucommon > u2:
		print('Second')
	else:
		print('Tie')


import math
t = int(input())
for i in range(t):
	n = int(input())
	p = [int(x) for x in input().split(' ')]
	first_num = 0
	second_num = 0
	common_num = 0
	for j in range(n):
		if p[j] != j + 1:
			first_num += 1
		if p[j] != n - j:
			second_num += 1
		if p[j] != j + 1 and p[j] != n - j:
			common_num += 1
	if first_num <= second_num:
		if common_num <= second_num - first_num:
			print('First')
		else:
			print('Tie')
	elif common_num < first_num - second_num:
		print('Second')
	else:
		print('Tie')


t = int(input(''))
for i in range(t):
	n = int(input(''))
	l = input('').split(' ')
	l = [int(x) for x in l]
	one = 0
	two = 0
	neu = 0
	bot = 0
	for i in range(n):
		v1 = l[i] == i + 1
		v2 = l[i] == n - i
		if v1 and v2:
			bot += 1
		elif v1:
			two += 1
		elif v2:
			one += 1
		else:
			neu += 1
	if one + neu <= two:
		print('First')
	elif two + neu < one:
		print('Second')
	else:
		print('Tie')


n = int(input())
for i in range(0, n):
	t = int(input())
	a = list(map(int, input().split()))
	a0 = 0
	b0 = 0
	a1 = 0
	b1 = 0
	for j in range(0, t):
		if a[j] != j + 1 and a[j] != t - j:
			a1 += 1
			b1 += 1
		if a[j] != j + 1 and a[j] == t - j:
			a0 += 1
		if a[j] == j + 1 and a[j] != t - j:
			b0 += 1
	if a0 + a1 <= b0:
		print('First')
	elif b0 + b1 <= a0 - 1:
		print('Second')
	else:
		print('Tie')


for _ in range(int(input())):
	num = int(input())
	numbers = [int(a) for a in input().split()]
	changeasc = 0
	changedesc = 0
	changeboth = 0
	ascnumbers = sorted(numbers)
	descnumbers = ascnumbers[::-1]
	for i in range(num):
		if numbers[i] != ascnumbers[i] and numbers[i] != descnumbers[i]:
			changeboth += 1
		elif numbers[i] != ascnumbers[i]:
			changeasc += 1
		elif numbers[i] != descnumbers[i]:
			changedesc += 1
	if changeasc + changeboth <= changedesc:
		print('First')
	elif changedesc + changeboth < changeasc:
		print('Second')
	else:
		print('Tie')


a = input()
for p in range(int(a)):
	n = int(input())
	L = input().split(' ')
	p1 = 0
	p2 = 0
	over = 0
	for i in range(1, n + 1):
		if int(L[i - 1]) != i and int(L[i - 1]) != n - i + 1:
			over += 1
		elif int(L[i - 1]) != i:
			p1 += 1
		elif int(L[i - 1]) != n - i + 1:
			p2 += 1
	if p1 + over <= p2:
		print('First')
	elif p2 + over < p1:
		print('Second')
	else:
		print('Tie')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	firstpos = secondpos = a = 0
	for i in range(n):
		if arr[i] != i + 1:
			firstpos += 1
		if arr[i] != n - i:
			secondpos += 1
		if arr[i] != i + 1 and arr[i] != n - i:
			a += 1
	if firstpos <= secondpos - a:
		print('First')
	elif secondpos < firstpos - a:
		print('Second')
	else:
		print('Tie')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = 0
	b = 0
	c = 0
	x = 1
	y = n
	for i in range(n):
		if arr[i] == x and arr[i] != y:
			b += 1
		elif arr[i] != x and arr[i] == y:
			a += 1
		elif arr[i] != x and arr[i] != y:
			c += 1
		x += 1
		y -= 1
	if a <= b:
		if c + a <= b:
			print('First')
		else:
			print('Tie')
	elif c + b < a:
		print('Second')
	else:
		print('Tie')


t = int(input())
for tes in range(t):
	n = int(input())
	first = 0
	end = 0
	comm = 0
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
		if a[i] != i and n - a[i] != i + 1:
			comm += 1
		if a[i] != i:
			first += 1
		if n - a[i] != i + 1:
			end += 1
	if first + comm <= end:
		print('First')
	elif end + comm < first:
		print('Second')
	else:
		print('Tie')


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s1 = 0
	s2 = 0
	countt = 0
	for x in range(n):
		if arr[x] == x + 1:
			s1 += 1
		if arr[x] == n - x:
			s2 += 1
		if n - x != arr[x] != x + 1:
			countt += 1
	l1 = n - s1 - countt
	l2 = n - s2 - countt
	if l1 + countt <= l2:
		print('First')
	elif l2 + countt < l1:
		print('Second')
	elif countt == 0 and l2 == l1 - 1:
		print('Second')
	else:
		print('Tie')


t = int(input())
while t > 0:
	n = int(input())
	rang = []
	line = input()
	nums = [int(_) for _ in line.split(' ')]
	A = [0] * (n + 1)
	B = [0] * (n + 1)
	c = 0
	for (i, num) in enumerate(nums):
		if num != i + 1:
			A[i + 1] = 1
		if num != n - i:
			B[i + 1] = 1
		if A[i + 1] and B[i + 1]:
			c += 1
	a = sum(A)
	b = sum(B)
	if a <= b - c:
		print('First')
	elif b < a - c:
		print('Second')
	else:
		print('Tie')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	t1 = 0
	t2 = 0
	c = 0
	for i in range(n):
		if l[i] != i + 1:
			t1 += 1
		if l[i] != n - i:
			t2 += 1
		if l[i] != i + 1 and l[i] != n - i:
			t1 -= 1
			t2 -= 1
			c += 1
	if t1 + c <= t2:
		print('First')
	elif c + t2 < t1:
		print('Second')
	else:
		print('Tie')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pos_left = 0
	pos_right = 0
	common = 0
	for x in range(n):
		if arr[x] != n - x and arr[x] != x + 1:
			common += 1
		if arr[x] != x + 1 and arr[x] == n - x:
			pos_left += 1
		if arr[x] != n - x and arr[x] == x + 1:
			pos_right += 1
	if pos_right + common < pos_left:
		print('Second')
		continue
	if pos_left + common <= pos_right:
		print('First')
		continue
	print('Tie')


from collections import defaultdict
from math import ceil, floor
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	la = sorted(l)
	ld = sorted(l, reverse=True)
	lx = []
	ly = []
	for j in range(n):
		if l[j] != la[j]:
			lx.append(l[j])
		if l[j] != ld[j]:
			ly.append(l[j])
	s = set(lx + ly)
	x = len(lx)
	y = len(ly)
	z = x + y - len(s)
	if z == 0:
		if x <= y:
			print('First')
		else:
			print('Second')
	elif x > y:
		if x - y <= z:
			print('Tie')
		else:
			print('Second')
	elif y - x < z:
		print('Tie')
	else:
		print('First')


t = int(input())

def countPerm(perm, n):
	(p1, p2, common) = (0, 0, 0)
	for (i, (i1, i2)) in enumerate(zip(list(range(n)), list(range(n - 1, -1, -1)))):
		if perm[i] != i1 and perm[i] != i2:
			common += 1
		elif perm[i] != i1:
			p1 += 1
		elif perm[i] != i2:
			p2 += 1
	return (p1, p2, common)

def play(t1, t2, comm):
	j = 0
	t = [t1, t2]
	while True:
		if t[j] == 0 and comm == 0:
			return j
		elif t[j] > 0:
			t[j] -= 1
		elif t[(j + 1) % 2] != 0 or comm != 1:
			comm -= 1
		else:
			return -1
		j = (j + 1) % 2
for _ in range(t):
	n = int(input())
	perm = [int(v) - 1 for v in input().split()]
	(p1, p2, comm) = countPerm(perm, n)
	win = play(p1, p2, comm)
	if win == 0:
		print('First')
	elif win == 1:
		print('Second')
	else:
		print('Tie')


n = int(input())
for i in range(n):
	(up, down) = ({}, {})
	m = int(input())
	lst = list(map(int, input().split()))
	for j in range(m):
		if lst[j] != j + 1:
			up[j] = 0
		if lst[m - 1 - j] != j + 1:
			down[j] = 0
	(diffUp, diffDown) = ({}, {})
	same = {}
	for term in up:
		if term not in down:
			diffUp[term] = 0
	for term in down:
		if term not in up:
			diffDown[term] = 0
		else:
			same[term] = 0
	if len(same) + len(diffUp) <= len(diffDown):
		print('First')
	elif len(same) + len(diffDown) < len(diffUp):
		print('Second')
	else:
		print('Tie')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(first, second) = (set(), set())
	for i in range(n):
		if i + 1 != a[i]:
			first.add(i + 1)
	for i in range(n - 1, -1, -1):
		if n - i != a[i]:
			second.add(i + 1)
	common = first.intersection(second)
	first.difference_update(common)
	second.difference_update(common)
	turn = 1
	while (len(common) != 0 or len(first) != 0) and (len(common) != 0 or len(second) != 0):
		if turn % 2:
			if len(first) != 0:
				first.pop()
			else:
				common.pop()
		elif len(second) != 0:
			second.pop()
		else:
			common.pop()
		turn += 1
	if turn % 2 == 0:
		if len(second) == 0:
			print('Tie')
		else:
			print('First')
	elif len(first) == 0:
		print('Tie')
	else:
		print('Second')