题目描述

Evelyn and Todd play a game with a multiset $S$ of integers, and an array $v$ which is initially empty. After deciding who plays first, they take turns alternately. In each turn, the corresponding player chooses any element of $S$, appends it to the end of $v$, and removes it from $S$.

The game ends as soon as $S$ is empty. At that moment, the number of inversions in $v$ is counted, that is, the number of pairs of indices $i < j$ such that $v_i > v_j$. If there are an even number of inversions then Evelyn is the winner, while Todd wins if the number of inversions is odd.

Evelyn and Todd have been playing the game for quite some time, and now both play optimally. Thus, for a given multiset $S$, there are four possible outcomes:

• Evelyn wins, regardless of who plays first.
• Todd wins, regardless of who plays first.
• The first player wins, regardless of who they are.
• The second player wins, regardless of who they are.

Given $S$, your task is to find which of the four cases will occur.

输入格式

The first line contains an integer $N$ ($1 \le N \le 10^5$) indicating the number of elements of the multiset $S$.

The second line contains $N$ integers $S_1, S_2, \ldots, S_N$ ($1 \le S_i \le N$ for $i = 1, 2, \ldots, N$), representing the elements of $S$.

输出格式

Output a single line with an uppercase letter indicating the outcome of the game, assuming that Evelyn and Todd play optimally. The letter must be:

• “E” if Evelyn wins;
• “T” if Todd wins;
• “F” if the first player wins; and
• “S” if the second player wins.

3
1 1 1

E

3
3 1 2

S

提示

Explanation of Sample 1:

No matter how Evelyn and Todd choose the elements of $S = \{1, 1, 1\}$, the resulting array will be $v = [1, 1, 1]$. Since there are no inversions in $v$, Evelyn wins, regardless of who plays first.