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

using namespace std;

#define ll long long
#define pii pair<ll, int>

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    cin>>n;

    pii a[n];
    map<int, ll> cnt;
    ll sum = 0;
    set<ll> st;
    for (int i=0; i<n; ++i) {
        int x;
        cin>>x;

        a[i] = {x, i};
        ++cnt[x];
        sum += (ll)(x);
        st.insert(x);
    }
    sort(a, a+n, greater<pii>());

    bool ans[n];
    fill(ans, ans+n, false);

    ll last = a[0].first;
    for (int i=0; i<n; ++i) {

        if (st.lower_bound(a[i].first) == st.begin()) {
            sum -= cnt[a[i].first]*a[i].first;
            cnt[a[i].first] = 0;

            //cout<<"got "<<sum<<": "<<i<<endl;
            if (sum+a[i].first > last) {
                ans[a[i].second] = true;
                last = a[i].first;
            } else break;
        } else {
            //cout<<"have "<<sum<<": "<<i<<endl;
            if (sum > last) {
                ans[a[i].second] = true;
                last = a[i].first;
            }

            //cout<<"wtf: "<<a[i+1].first<<", "<<a[i].first<<endl;
            if (i < n-1 && a[i+1].first < a[i].first) {
                sum -= cnt[a[i].first]*a[i].first;
                cnt[a[i].first] = 0;  
            }
        }
    }

    for (int i=0; i<n; ++i) {
        if (ans[i]) cout<<"T";
        else cout<<"N";
    }
    cout<<endl;
}