CF1772E.Permutation Game

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.

两名玩家正在进行一场比赛。他们拥有一个由整数 $1, 2, \dots, n$ 构成的排列（即一个数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次）。该排列既不是升序排列，也不是降序排列（即该排列既不是 $[1, 2, \dots, n]$，也不是 $[n, n-1, \dots, 1]$）。

初始时，排列中所有元素均为红色。双方轮流行动。在自己的回合中，玩家可执行以下三种操作之一：

• 重新排列排列中的元素，使得所有红色元素保持其原有位置（注意：蓝色元素之间可以相互交换，但并非必须交换）；
• 将一个红色元素的颜色更改为蓝色；
• 跳过本轮行动。

若排列变为升序排列（即变为 $[1, 2, \dots, n]$），则先手玩家获胜；
若排列变为降序排列（即变为 $[n, n-1, \dots, 1]$），则后手玩家获胜；
若游戏持续 $100^{500}$ 回合而无人获胜，则以平局结束。

你的任务是：假设双方均采用最优策略，判断该游戏的结果。

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$.

第一行包含一个整数 $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$。

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.

对于每个测试用例，若先手玩家获胜，则输出 First；若后手玩家获胜，则输出 Second；若结果为平局，则输出 Tie。

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.

我们来说明在第一个例子中先手玩家如何获胜。

他们应在前两回合将元素 $3$ 和 $4$ 染成蓝色，随后便可对蓝色元素重新排序，使排列变为 $[1, 2, 3, 4]$。后手玩家既无法干扰这一策略，也无法更快取胜。