Problem Description

There are $n$ fish, where the mass of the $i$-th fish is $a_i$ grams.

Fish $x$ can eat fish $y$ if and only if $a_x > a_y$.

If $x$ eats $y$, then $y$ disappears, and $a_x$ becomes $a_x + a_y$.

You may choose the order of eating freely until only one fish remains.

For each fish, determine whether it is possible for it to be the only fish left at the end. If it is impossible to end up with only one fish, then no fish satisfies this condition.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output one line containing a string $s$ of length $n$, where $s_i = \text{T}$ means the $i$-th fish satisfies the condition above, and $s_i = \text{N}$ means it does not.

6
2 7 1 8 2 8

NTNTNT

3
5 4 4

TNN

Hint

Sample #1 Explanation

Below, $x \rightarrow y$ means that $x$ eats $y$.

One possible sequence that leaves fish $2$ is: $2 \rightarrow 1, 2 \rightarrow 3, 2 \rightarrow 4, 2 \rightarrow 5, 2 \rightarrow 6$.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5