题目描述

Evelyn 和 Todd 在一个整数多重集 $S$ 和一个初始为空的数组 $v$ 上玩游戏。决定谁先手后，两人轮流操作。每轮中，当前玩家从 $S$ 中选择任意一个元素，将其追加到 $v$ 的末尾，并从 $S$ 中移除该元素。

游戏在 $S$ 为空时结束。此时，统计 $v$ 中的逆序对数量，即满足 $i < j$ 且 $v_i > v_j$ 的下标对 $(i, j)$ 的个数。若逆序对数为偶数，则 Evelyn 获胜；若为奇数，则 Todd 获胜。

Evelyn 和 Todd 已经玩了相当长的时间，现在两人都采取最优策略。因此，对于给定的多重集 $S$，有四种可能的结果：

• 无论谁先手，Evelyn 都获胜。
• 无论谁先手，Todd 都获胜。
• 无论先手是谁，先手玩家都获胜。
• 无论先手是谁，后手玩家都获胜。

给定 $S$，你的任务是判断这四种情况中的哪一种会发生。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示多重集 $S$ 中元素的个数。

第二行包含 $N$ 个整数 $S_1, S_2, \ldots, S_N$（对于 $i = 1, 2, \ldots, N$，有 $1 \le S_i \le N$），表示 $S$ 中的元素。

输出格式

输出一行一个大写字母，表示在 Evelyn 和 Todd 都采取最优策略时的游戏结果。字母的含义如下：

• “E”：Evelyn 获胜；
• “T”：Todd 获胜；
• “F”：先手玩家获胜；
• “S”：后手玩家获胜。

3
1 1 1

E

3
3 1 2

S

提示

样例 1 解释：

无论 Evelyn 和 Todd 如何选择 $S = \{1, 1, 1\}$ 中的元素，最终得到的数组都是 $v = [1, 1, 1]$。由于 $v$ 中没有逆序对，因此无论谁先手，Evelyn 都获胜。

翻译由 DeepSeek V4 Pro 完成