题目描述

有 $n$ 条鱼，第 $i$ 条的重量为 $a_i$ 克。

$x$ 能吃掉 $y$ 当且仅当 $a_x > a_y$，一旦 $x$ 吃了 $y$，$y$ 会消失，$a_x$ 则变为 $a_x + a_y$。

你可以随意指定吃鱼的顺序，直至留下一条鱼为止。

询问每一条鱼是否可能被留下。

输入格式
第一行一个正整数 $n$，表示序列长度。
第二行 $n$ 个整数 $a_i$。

输出格式
一行一个长度为 $n$ 的字符串，其中 $s_i = \text{T}$ 表示第 $i$ 条鱼可能被留下，$s_i = \text{N}$ 表示第 $i$ 条鱼不可能被留下。

样例 1
输入

6
2 7 1 8 2 8

输出

NTNTNT

下面用 $x \rightarrow y$ 表示 $x$ 吃 $y$。

把 $2$ 号鱼留下的一种方案如下：$2 \rightarrow 1$，$2 \rightarrow 3$，$2 \rightarrow 4$，$2 \rightarrow 5$，$2 \rightarrow 6$。

而 $5$ 号鱼无论如何也留不下。

样例 2
输入

3
5 4 4

输出

TNN

注意 $x$ 能吃掉 $y$ 当且仅当 $a_x > a_y$，不取等号。

数据范围与提示
$2 \leq n \leq 5 \times 10^5$
$1 \leq a_i \leq 10^9$