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

using namespace std;

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

    int n; 

    cin >> n;

    long long * tab = new long long[n];
    long long * vec_sum = new long long[n];
    char * result = new char[n];

    vector< pair <long long, int> > vec;

    long long max = 0;
    long long min = 1000000001;

    for (int i = 0; i < n; ++i) {
        cin >> tab[i];
        if (tab[i] < min) {
            min = tab[i];
        }
        
        if (tab[i] > max) {
            max = tab[i];
        }
        
        result[i] = 'N';
        vec_sum[i] = 0;
        vec.push_back(make_pair(tab[i], i));
    }

    if (min == max) {
        for (int i = 0; i < n; ++i) {
            cout << result[i];
        }
        return 0;
    }

    sort(vec.begin(), vec.end(), [](pair <long long, int> &x, pair <long long, int> &y){
        return x.first < y.first;
    });

    long long prev_sum = 0;
    for(vector< pair <long long, int> >::iterator it = vec.begin(); it != vec.end(); ++it) {
        prev_sum += it->first;
        vec_sum[it->second] = prev_sum;
    }
    
    vector< pair <long long, int> >::iterator first_gt_min = upper_bound(vec.begin(), vec.end(), min, [](long long x, const pair <long long, int> &y){
        return x < y.first;
    });
    vector< pair <long long, int> >::iterator first_max = lower_bound(vec.begin(), vec.end(), max, [](const pair <long long, int> &y, long long x){
        return x > y.first;
    });

    for(vector< pair <long long, int> >::iterator it = first_max; it != vec.end(); ++it) {
        // cerr << "d(" << it->first << ", " << it->second << ")" << endl;
        result[it->second] = 'T';
    }

    vector< pair <long long, int> >::iterator prev = first_max;
    vector< pair <long long, int> >::iterator it = --first_max;
    vector< pair <long long, int> >::iterator end = --first_gt_min;
    
    while (it != end) {
        // cerr << "PREV_SUM = (" << vec_sum[prev->second] << ")" << endl;
        // cerr << "DEB_SUM = (" << it->first << ", " << it->second << ", " << vec_sum[it->second] << ")" << endl;
        if (vec_sum[it->second] > prev->first) {
            result[it->second] = 'T';
        } else {
            break;
        }
        prev = it;
        --it;
    }

    
    for (int i = 0; i < n; ++i) {
         cout << result[i];
    }
    
    return 0;
}