I. Inversion Game
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt j$$$ such that $$$v_i \gt 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.
Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 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 \leq S_i \leq N$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), representing the elements of $$$S$$$.

Output

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.
Examples
Input
3
1 1 1
Output
E
Input
3
3 1 2
Output
S
Note

Explanation for example 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.