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
#include <bits/stdc++.h>

using namespace std;

template<typename It>
bool king(It first, It last, int v0) {
    bool found_self = false;
    int64_t v = v0;
    while(first != last) {
        auto x = *first++;
        if(x == v0 and not found_self)
            found_self = true;
        else if(v > x)
            v += x;
        else
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    size_t n;
    cin >> n;

    vector<int> A(n);
    for(auto& a : A)
        cin >> a;

    auto V = A;
    sort(V.begin(), V.end());

    size_t lo = 0, hi = V.size();
    while(lo < hi) {
        auto mid = (lo + hi) / 2;
        if(king(V.begin(), V.end(), V[mid]))
            hi = mid;
        else
            lo = mid+1;
    }
    V.push_back(INT_MAX);

    for(auto a : A)
        cout << (a >= V[lo] ? 'T' : 'N');
    cout << endl;
}