Два игрока играют в игру. У них есть перестановка чисел \(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}\) ходов и никто не выигрывает, она заканчивается вничью.
Ваша задача — определить результат игры при оптимальной игре обоих игроков.
Выходные данные
Для каждого набора входных данных выведите First, если победу одержит первый игрок, Second, если победу одержит второй игрок, и Tie, если результатом будет ничья.
Примечание
Давайте покажем, как первый игрок выигрывает в первом примере.
Он должен покрасить элементы \(3\) и \(4\) в синий цвет в течение первых двух ходов, а затем он может изменить порядок синих элементов таким образом, чтобы перестановка стала равна \([1, 2, 3, 4]\). Второй игрок не может ни вмешаться в эту стратегию, ни выиграть быстрее.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|