310016: CF1772E. Permutation Game
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Permutation Game
题意翻译
有一个长度为 $n$ 的仅为 $1\sim n$ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种： - 将某个数变成蓝色。 - 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。 - 跳过此次操作。 两个玩家依次进行一次操作视为一个回合，游戏共进行 $100^{500}$ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $100^{500}$ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。 ### 输入格式 第一个数为 $t$（$1\le t\le10^5$）表示数据组数。 对于每一组数据，第一行一个数 $n$，表示序列长度，下一行 $n$ 个数表示初始序列。 ### 输出格式 如果第一个操作玩家胜利，输出 ```First ```，如果第二个玩家操作胜利，输出 ```Second```，平局输出 ```Tie```。题目描述
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.
输入输出样例
输入样例 #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.Input
题意翻译
有一个长度为 $n$ 的仅为 $1\sim n$ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种： - 将某个数变成蓝色。 - 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。 - 跳过此次操作。 两个玩家依次进行一次操作视为一个回合，游戏共进行 $100^{500}$ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $100^{500}$ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。 ### 输入格式 第一个数为 $t$（$1\le t\le10^5$）表示数据组数。 对于每一组数据，第一行一个数 $n$，表示序列长度，下一行 $n$ 个数表示初始序列。 ### 输出格式 如果第一个操作玩家胜利，输出 ```First ```，如果第二个玩家操作胜利，输出 ```Second```，平局输出 ```Tie```。Output
**排列游戏**
**题意翻译**
有一个长度为 $ n $ 的仅为 $ 1\sim n $ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种：
- 将某个数变成蓝色。
- 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。
- 跳过此次操作。
两个玩家依次进行一次操作视为一个回合，游戏共进行 $ 100^{500} $ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $ 100^{500} $ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。
**输入格式**
第一个数为 $ t $（$ 1\le t\le10^5 $）表示数据组数。
对于每一组数据，第一行一个数 $ n $，表示序列长度，下一行 $ n $ 个数表示初始序列。
**输出格式**
如果第一个操作玩家胜利，输出 `First`，如果第二个玩家操作胜利，输出 `Second`，平局输出 `Tie`。
**题目描述**
两个玩家正在玩一个游戏。他们有一个整数排列 $ 1, 2, ..., n $ （排列是每个元素从 $ 1 $ 到 $ n $ 只出现一次的数组，排列既不是升序也不是降序（即排列不是 $ [1, 2, \dots, n] $ 或 $ [n, n-1, \dots, 1] $ ）。
最初，排列的所有元素都是红色的。玩家轮流进行。在他们的回合中，玩家可以进行以下三种行动之一：
- 重新排列排列的元素，使得所有红色的元素保持他们的位置（注意蓝色元素可以相互交换，但这不是强制的）。
- 将一个红色元素的颜色改为蓝色。
- 跳过这个回合。
如果排列是升序的（即它变为 $ [1, 2, \dots, n] $ ），则第一个玩家获胜。如果排列是降序的（即它变为 $ [n, n-1, \dots, 1] $ ），则第二个玩家获胜。如果游戏进行了 $ 100^{500} $ 回合而没有人获胜，则以平局结束。
如果两个玩家都采取最优策略，你的任务是确定游戏的结果。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $。
**输出格式**
对于每个测试用例，如果第一个玩家获胜，则打印 `First`，如果第二个玩家获胜，则打印 `Second`，如果结果是平局，则打印 `Tie`。
**输入输出样例**
**输入样例 #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
```
**说明**
让我们展示一下第一个玩家如何在第一个示例中获胜。
他们应该在他们的前两个回合中将元素 $ 3 $ 和 $ 4 $ 变为蓝色，然后他们可以以这种方式重新排列蓝色元素，使得排列变为 $ [1, 2, 3, 4] $。第二个玩家既不能干扰这个策略，也不能更快获胜。**排列游戏** **题意翻译** 有一个长度为 $ n $ 的仅为 $ 1\sim n $ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种： - 将某个数变成蓝色。 - 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。 - 跳过此次操作。 两个玩家依次进行一次操作视为一个回合，游戏共进行 $ 100^{500} $ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $ 100^{500} $ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。 **输入格式** 第一个数为 $ t $（$ 1\le t\le10^5 $）表示数据组数。 对于每一组数据，第一行一个数 $ n $，表示序列长度，下一行 $ n $ 个数表示初始序列。 **输出格式** 如果第一个操作玩家胜利，输出 `First`，如果第二个玩家操作胜利，输出 `Second`，平局输出 `Tie`。 **题目描述** 两个玩家正在玩一个游戏。他们有一个整数排列 $ 1, 2, ..., n $ （排列是每个元素从 $ 1 $ 到 $ n $ 只出现一次的数组，排列既不是升序也不是降序（即排列不是 $ [1, 2, \dots, n] $ 或 $ [n, n-1, \dots, 1] $ ）。 最初，排列的所有元素都是红色的。玩家轮流进行。在他们的回合中，玩家可以进行以下三种行动之一： - 重新排列排列的元素，使得所有红色的元素保持他们的位置（注意蓝色元素可以相互交换，但这不是强制的）。 - 将一个红色元素的颜色改为蓝色。 - 跳过这个回合。 如果排列是升序的（即它变为 $ [1, 2, \dots, n] $ ），则第一个玩家获胜。如果排列是降序的（即它变为 $ [n, n-1, \dots, 1] $ ），则第二个玩家获胜。如果游戏进行了 $ 100^{500} $ 回合而没有人获胜，则以平局结束。 如果两个玩家都采取最优策略，你的任务是确定游戏的结果。 **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $。 **输出格式** 对于每个测试用例，如果第一个玩家获胜，则打印 `First`，如果第二个玩家获胜，则打印 `Second`，如果结果是平局，则打印 `Tie`。 **输入输出样例** **输入样例 #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 ``` **说明** 让我们展示一下第一个玩家如何在第一个示例中获胜。 他们应该在他们的前两个回合中将元素 $ 3 $ 和 $ 4 $ 变为蓝色，然后他们可以以这种方式重新排列蓝色元素，使得排列变为 $ [1, 2, 3, 4] $。第二个玩家既不能干扰这个策略，也不能更快获胜。
**题意翻译**
有一个长度为 $ n $ 的仅为 $ 1\sim n $ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种：
- 将某个数变成蓝色。
- 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。
- 跳过此次操作。
两个玩家依次进行一次操作视为一个回合，游戏共进行 $ 100^{500} $ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $ 100^{500} $ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。
**输入格式**
第一个数为 $ t $（$ 1\le t\le10^5 $）表示数据组数。
对于每一组数据，第一行一个数 $ n $，表示序列长度，下一行 $ n $ 个数表示初始序列。
**输出格式**
如果第一个操作玩家胜利，输出 `First`，如果第二个玩家操作胜利，输出 `Second`，平局输出 `Tie`。
**题目描述**
两个玩家正在玩一个游戏。他们有一个整数排列 $ 1, 2, ..., n $ （排列是每个元素从 $ 1 $ 到 $ n $ 只出现一次的数组，排列既不是升序也不是降序（即排列不是 $ [1, 2, \dots, n] $ 或 $ [n, n-1, \dots, 1] $ ）。
最初，排列的所有元素都是红色的。玩家轮流进行。在他们的回合中，玩家可以进行以下三种行动之一：
- 重新排列排列的元素，使得所有红色的元素保持他们的位置（注意蓝色元素可以相互交换，但这不是强制的）。
- 将一个红色元素的颜色改为蓝色。
- 跳过这个回合。
如果排列是升序的（即它变为 $ [1, 2, \dots, n] $ ），则第一个玩家获胜。如果排列是降序的（即它变为 $ [n, n-1, \dots, 1] $ ），则第二个玩家获胜。如果游戏进行了 $ 100^{500} $ 回合而没有人获胜，则以平局结束。
如果两个玩家都采取最优策略，你的任务是确定游戏的结果。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $。
**输出格式**
对于每个测试用例，如果第一个玩家获胜，则打印 `First`，如果第二个玩家获胜，则打印 `Second`，如果结果是平局，则打印 `Tie`。
**输入输出样例**
**输入样例 #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
```
**说明**
让我们展示一下第一个玩家如何在第一个示例中获胜。
他们应该在他们的前两个回合中将元素 $ 3 $ 和 $ 4 $ 变为蓝色，然后他们可以以这种方式重新排列蓝色元素，使得排列变为 $ [1, 2, 3, 4] $。第二个玩家既不能干扰这个策略，也不能更快获胜。**排列游戏** **题意翻译** 有一个长度为 $ n $ 的仅为 $ 1\sim n $ 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种： - 将某个数变成蓝色。 - 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。 - 跳过此次操作。 两个玩家依次进行一次操作视为一个回合，游戏共进行 $ 100^{500} $ 回合。在游戏任何时刻，如果当前序列为 $\{1,2,3...,n\}$，则第一个操作的玩家胜利。如果当前序列为 $\{n,n-1,n-2...1\}$，则第二个玩家胜利。进行 $ 100^{500} $ 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。 **输入格式** 第一个数为 $ t $（$ 1\le t\le10^5 $）表示数据组数。 对于每一组数据，第一行一个数 $ n $，表示序列长度，下一行 $ n $ 个数表示初始序列。 **输出格式** 如果第一个操作玩家胜利，输出 `First`，如果第二个玩家操作胜利，输出 `Second`，平局输出 `Tie`。 **题目描述** 两个玩家正在玩一个游戏。他们有一个整数排列 $ 1, 2, ..., n $ （排列是每个元素从 $ 1 $ 到 $ n $ 只出现一次的数组，排列既不是升序也不是降序（即排列不是 $ [1, 2, \dots, n] $ 或 $ [n, n-1, \dots, 1] $ ）。 最初，排列的所有元素都是红色的。玩家轮流进行。在他们的回合中，玩家可以进行以下三种行动之一： - 重新排列排列的元素，使得所有红色的元素保持他们的位置（注意蓝色元素可以相互交换，但这不是强制的）。 - 将一个红色元素的颜色改为蓝色。 - 跳过这个回合。 如果排列是升序的（即它变为 $ [1, 2, \dots, n] $ ），则第一个玩家获胜。如果排列是降序的（即它变为 $ [n, n-1, \dots, 1] $ ），则第二个玩家获胜。如果游戏进行了 $ 100^{500} $ 回合而没有人获胜，则以平局结束。 如果两个玩家都采取最优策略，你的任务是确定游戏的结果。 **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $。 **输出格式** 对于每个测试用例，如果第一个玩家获胜，则打印 `First`，如果第二个玩家获胜，则打印 `Second`，如果结果是平局，则打印 `Tie`。 **输入输出样例** **输入样例 #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 ``` **说明** 让我们展示一下第一个玩家如何在第一个示例中获胜。 他们应该在他们的前两个回合中将元素 $ 3 $ 和 $ 4 $ 变为蓝色，然后他们可以以这种方式重新排列蓝色元素，使得排列变为 $ [1, 2, 3, 4] $。第二个玩家既不能干扰这个策略，也不能更快获胜。