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
#include <iostream>
#include <vector>
#include <algorithm>

#ifdef TEST_MODE
#include <fstream>
#endif

using namespace std;

typedef long long ll;



struct Sum {
    ll weight;
    ll possibleWeight = 0;
    bool canBeKing = false;
    int originalOrder;
    bool operator > (const Sum& sum) const {
            return (weight > sum.weight);
        }
    bool operator == (const Sum& sum) const {
            return (weight == sum.weight);
        }
};

int main() {
#ifdef TEST_MODE
    std::ifstream in("1.in"); std::cin.rdbuf(in.rdbuf());
#endif
    std::ios_base::sync_with_stdio(false);
    
    const int kMaxNoSums = 500000;
    char results[kMaxNoSums];
    
    vector<Sum> sums;
    int n;
    cin >> n;
    
    for ( int i = 0; i < n; ++ i ) {
        Sum sum;
        cin >> sum.weight;
        sum.originalOrder = i;
        sums.push_back(sum);
    }
    
    sort(sums.begin(), sums.end(), greater<Sum>());
    
    ll possibleWeight = 0;
    for ( int i = n - 1; i >= 0; --i ){
        int beginRange = i;
        int endRange = i;
        
        while ( i > 0 && sums[i] == sums[i-1] ) {
            endRange = i - 1;
            possibleWeight += sums[i].weight;
            i--;
        }
        possibleWeight += sums[endRange].weight;
        for ( int j = beginRange; j >= endRange; --j) {
            sums[j].possibleWeight = possibleWeight;
        }
    }
    
    if ( sums.front() > sums.back() ) {
        results[sums.front().originalOrder] = 'T';
        sums.front().canBeKing = true;
        for ( int i = 1; i < n; ++i ) {
            if ( sums[i-1].canBeKing && sums[i] > sums[n-1] && sums[i].possibleWeight > sums[i-1].weight) {
                sums[i].canBeKing = true;
                results[sums[i].originalOrder] = 'T';
            } else {
                sums[i].canBeKing = false;
                results[sums[i].originalOrder] = 'N';
            }
        }
        for ( int i = 0; i < n; ++i ) {
            cout << results[i];
        }
        cout << endl;
    } else {
        for ( int i = 0; i < n; ++i )
            cout << 'N';
        cout << endl;
    }
    return 0;
}