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.

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

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.

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.