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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;


struct Sum {
    unsigned long long weight;
    unsigned long long count;

    Sum(unsigned long long weight, unsigned long long count) {
        this->weight = weight;
        this->count = count;
    }
};


int main(int argc, char const *argv[]) {
    int n;
    int original_sums[500001];
    map<unsigned long long, unsigned long long> sums;
    map<unsigned long long, char> results_map;
    scanf("%d", &n);

    for(int i=0; i<n; i++) {
        unsigned long long w;
        scanf("%lld", &w);

        original_sums[i] = w;

        if (sums.count(w)) {
            sums[w]++;
        } else {
            sums[w] = 1;
        }
    }

    if (sums.size() == 1 && n != 1) {
        for (int i = 0; i < n; i++) {
            printf("N");
        }

        return 0;
    }

    vector<Sum> sums_vector;

    for (auto &&sum : sums)  {
        sums_vector.push_back(Sum(sum.first, sum.second));
        results_map[sum.first] = 'N';
        // printf("%d %d\n", sum.first, sum.second);
    }

    sort(
        sums_vector.begin(),
        sums_vector.end(),
        [](Sum const &a, Sum const &b) {
            return a.weight < b.weight;
        }
    );

    unsigned long long* prefix_sums = new unsigned long long[sums_vector.size()];
    prefix_sums[0] = sums_vector[0].weight * sums_vector[0].count;

    for (int i=1; i < sums_vector.size(); i++) {
        prefix_sums[i] = prefix_sums[i - 1] + sums_vector[i].count * sums_vector[i].weight;
        // printf("%lld\n", prefix_sums[i]);
    }

    results_map[sums_vector[sums_vector.size() - 1].weight] = 'T';

    for (int i = sums_vector.size() - 2; i > 0; i--) {
        // printf("%lld %lld\n", prefix_sums[i], sums_vector[i + 1].weight);
        if (prefix_sums[i] > sums_vector[i + 1].weight) {
            results_map[sums_vector[i].weight] = 'T';
        } else {
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%c", results_map[original_sums[i]]);
    }
    
    puts("");

    return 0;
}