Permutation Game

4000ms

262144K

Description:

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.

Input:

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

Output:

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.

Sample Input:

4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4

Sample Output:

First
Tie
Second
Tie

Note:

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.

Informação

Provedor Codeforces

Código CF1772E