[AdditionalFile3606.zip](file://AdditionalFile3606.zip?type=additional_file)

#3606. 「PA 2021」Sumy

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2021 Runda 3 Sumy

有 $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

输出

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 \gt a_y$，不取等号。

数据范围与提示

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

$1 \leq a_i \leq 10 ^ 9$