题目描述

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

x 能吃掉 y 当且仅当 $a_x \gt 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

样例输出1

NTNTNT

样例 1

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

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

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

样例输入1

3
5 4 4

样例输出1

TNN

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

数据范围与提示

$2 \leq n \leq 5 \times 10 ^ 5$

$1 \leq a_i \leq 10 ^ 9$