1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define iamspeed ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

long long n, l, r, mid, roz, pref[500005], ind[500005], ile;
char res[500005];
pair<long long, long long> t[500005];
bool sprawdz(int x)
{
    x = ind[x];
    long long sum = pref[x];
    while(x < n)
    {
        x++;
        if(sum > t[x].st) sum += t[x].st;
        else break;
    }
    if(sum == ile) return 1;
    else return 0;
}

int main()
{
    iamspeed;
    cin >> n;
    l = 1; r = n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> t[i].st;
        ile += t[i].st;
        t[i].nd = i;
    }
    sort(t + 1, t + 1 + n);
    for(int i = 1 ; i <= n ; i++)
    {
        if(t[i].st != t[i - 1].st)
        {
            roz++;
            ind[i] = i;
        } 
        else ind[i] = ind[i - 1];
        pref[i] = pref[i - 1] + t[i].st;
    }
    while(l != r)
    {
        mid = (l + r) / 2;
        if(sprawdz(mid)) r = mid;
        else l = mid + 1;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(i < l) res[t[i].nd] = 'N';
        else res[t[i].nd] = 'T';
    }
    if(roz == 1)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cout <<"N"; 
        }
        return 0;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        cout << res[i]; 
    }
}