The Byteotian Sea is known for many species of fish, unseen in other waters of the world. It is most famous for the Byteotian catfish inhabiting it, specimens of which sometimes weigh even several tons!

Byteotian catfish are also characterized by a very unusual diet: when winter comes, they eat only other catfish living in the water!

Algolina is a PhD student at the University of Byteotia, and her research project is to study this behavior of the catfish. She has already managed to catch all the specimens in the Byteotian Sea, weigh them, and release them back into the water. The mass of each catfish, expressed in grams, is a positive integer. Furthermore, Algolina observed that a catfish can eat another catfish only if it is heavier than it. In other words, a catfish can feed only on catfish with a strictly smaller mass. At the moment one catfish eats another, lighter catfish, its mass increases to the sum of the masses of both catfish, and the eaten catfish disappears from the sea.

The time has come to analyze the research results. Algolina wonders if it might turn out that only one catfish remains in the Byteotian Sea. More precisely, if as a result of the above feeding process exactly one catfish remains in the water, this fish becomes the King of the Byteotian Sea. Naturally, the question arises: which fish can become the Kings of the Byteotian Sea?

Input

The first line of input contains a single integer $n$ ($2 \le n \le 500\,000$) denoting the number of catfish in the Byteotian Sea.

The second line consists of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) and describes the masses of the consecutive catfish in the sea – $a_i$ denotes the mass of the $i$-th catfish expressed in grams.

Output

In the first and only line of output, print a sequence of $n$ characters; the $i$-th character ($1 \le i \le n$) should be equal to T if the $i$-th catfish can become the King of the Byteotian Sea, and N otherwise.

Examples

Input 1

6
2 7 1 8 2 8

Output 1

NTNTNT

Input 2

3
5 4 4

Output 2

TNN

Note

Consider the first example. The following description shows a scenario in which the second catfish (weighing 7 grams) becomes the King of the Byteotian Sea:

It can be proven that the first catfish (with an initial weight of 2 grams) is not able to become the King. Note that in the second example, the second catfish (weighing 4 grams) cannot eat any other catfish, so it cannot become the King of the Byteotian Sea.