Sumy

Morze Bajtockie znane jest z wielu gatunków ryb, niespotykanych w innych akwenach wodnych świata. Najbardziej słynie z powodu zamieszkujących je bajtockich sumów, których okazy czasami ważą nawet kilka ton! Sumy bajtockie charakteryzuje również bardzo nietypowa dieta: gdy nadchodzi zima, zjadają one jedynie inne sumy żyjące w akwenie!

Algolina jest doktorantką Uniwersytetu Bajtockiego i jej projektem badawczym jest zbadanie tego zachowania sumów. Zdążyła już wyłapać wszystkie okazy z Morza Bajtockiego, zważyć je i wypuścić z powrotem do akwenu. Masa każdego suma, wyrażona w gramach, jest dodatnią liczbą całkowitą. Ponadto, Algolina zaobserwowała, że sum może zjeść innego suma tylko wtedy, gdy jest od niego cięższy. Innymi słowy, sum może żywić się jedynie sumami o ściśle mniejszej masie. W momencie, gdy jeden sum zje drugiego, lżejszego suma, jego masa wzrasta do sumy mas obu sumów, a zjedzony sum znika z morza.

Przyszedł czas na analizę wyników badań. Algolina zastanawia się, czy może się okazać, że w Morzu Bajtockim pozostanie tylko jeden sum. Dokładniej, jeśli w wyniku powyższego procesu żywienia się sumów w akwenie pozostanie dokładnie jeden sum, to ryba ta staje się królem Morza Bajtockiego. Naturalnie więc narzuca się pytanie: które ryby mogą stać się królami Morza Bajtockiego?

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 500 000) oznaczającą liczbę sumów w Morzu Bajtockim.

Drugi wiersz składa się z n liczb całkowitych a1, a2, . . . , an (1 ≤ ai ≤ 109) i opisuje masy kolejnych sumów w morzu – ai oznacza masę i-tego suma wyrażoną w gramach.

W pierwszym i jedynym wierszu wyjścia wypisz ciąg n znaków; i-ty znak opisu (1 ≤ i ≤ n) powinien być równy T, jeśli i-ty sum może stać się królem Morza Bajtockiego, zaś N w przeciwnym przypadku.

Wyjaśnienie przykładów: Rozważmy pierwszy przykład. Poniższy opis pokazuje scenariusz, w którym drugi sum (o wadze 7 gramów) staje się królem Morza Bajtockiego:

Można natomiast udowodnić, że pierwszy sum (o początkowej wadze 2 gramów) nie jest w stanie stać się królem.

Zwróć uwagę na to, że w drugim przykładzie drugi sum (o wadze 4 gramów) nie może zjeść żadnego innego suma, więc nie może on stać się królem Morza Bajtockiego.