E. Игра с перестановкой
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два игрока играют в игру. У них есть перестановка чисел $$$1$$$, $$$2$$$, ..., $$$n$$$ (перестановка — это массив, в котором каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз). Перестановка не отсортирована ни в прямом, ни в обратном порядке (т.е. перестановка не имеет вид $$$[1, 2, \dots, n]$$$ или $$$[n, n-1, \dots, 1]$$$).

Изначально все элементы перестановки покрашены в красный цвет. Игроки ходят по очереди. На своем ходу игрок может сделать одно из трех действий:

  • переставить элементы перестановки таким образом, что все красные элементы останутся на своих позициях (обратите внимание, что синие элементы можно менять местами друг с другом, но не обязательно);
  • покрасить любой красный элемент перестановки в синий цвет;
  • пропустить ход.

Первый игрок выигрывает, если перестановка окажется отсортирована в порядке возрастания (т.е. станет равна $$$[1, 2, \dots, n]$$$). Второй — если перестановка окажется отсортирована в порядке убывания (т.е. станет равна $$$[n, n-1, \dots, 1]$$$). Если игра длится $$$100^{500}$$$ ходов и никто не выигрывает, она заканчивается вничью.

Ваша задача — определить результат игры при оптимальной игре обоих игроков.

Входные данные

Первая строка содержит одно целое чисел $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — размер перестановки.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ — сама перестановка. Перестановка $$$p$$$ не отсортирована ни в прямом, ни в обратном порядке.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите First, если победу одержит первый игрок, Second, если победу одержит второй игрок, и Tie, если результатом будет ничья.

Пример
Входные данные
4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4
Выходные данные
First
Tie
Second
Tie
Примечание

Давайте покажем, как первый игрок выигрывает в первом примере.

Он должен покрасить элементы $$$3$$$ и $$$4$$$ в синий цвет в течение первых двух ходов, а затем он может изменить порядок синих элементов таким образом, чтобы перестановка стала равна $$$[1, 2, 3, 4]$$$. Второй игрок не может ни вмешаться в эту стратегию, ни выиграть быстрее.