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.