Codeforces Round 839 (Div. 3) |
---|
Закончено |
Два игрока играют в игру. У них есть перестановка чисел $$$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, если результатом будет ничья.
441 2 4 332 3 153 4 5 2 161 5 6 3 2 4
First Tie Second Tie
Давайте покажем, как первый игрок выигрывает в первом примере.
Он должен покрасить элементы $$$3$$$ и $$$4$$$ в синий цвет в течение первых двух ходов, а затем он может изменить порядок синих элементов таким образом, чтобы перестановка стала равна $$$[1, 2, 3, 4]$$$. Второй игрок не может ни вмешаться в эту стратегию, ни выиграть быстрее.
Название |
---|