P9050 [PA 2021] Sums

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.**

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

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.

#### 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