← 返回题目列表

Codeforces · 1772/E

E. 排列游戏

中文机器翻译题面 查看原题

两个玩家正在玩游戏。它们具有整数的排列 $$$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]$$$。第二个玩家既不能干扰这个策略,也不能更快地获胜。