A15619. 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.
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$ .
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.
输入输出样例
输入 #1
4 4 1 2 4 3 3 2 3 1 5 3 4 5 2 1 6 1 5 6 3 2 4
输出 #1
First Tie 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.
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.