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, \dots, S_N$ ($1 \le S_i \le N$，对于 $i = 1, 2, \dots, N$)，表示 $S$ 中的元素。

输出格式

输出单行，包含一个大写字母，表示在 Evelyn 和 Todd 都采取最优策略下游戏的结果。该字母必须为：

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

样例

输入样例 1

3
1 1 1

输出样例 1

E

说明 1

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

输入样例 2

3
3 1 2

输出样例 2

S