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
92
93
94
95
96
97
///MEMENTO MEMO, MEMENTO LONG LONG
#include <bits/stdc++.h>

#define DEBUG if(1)
#define COUT cout << "\e[36m"
#define ENDL "\e[39m" << endl
#define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] "
#define ST first
#define ND second
using namespace std;

typedef long long LL;

//struct Fish
//{
//    int size, pos;
//    bool king;
//};
//
//inline bool cmp_size(Fish a, Fish b)
//{
//
//}
int n;

bool can_king(LL nominee, const vector<int>& fishes)
{
    bool ate_himself = false;
    LL sum_weight = nominee;
    for (int i = n-1; i >= 0;--i)
    {
        if(!ate_himself && nominee == fishes[i])
        {
            ate_himself = true;
        }
        else
        {
            if (fishes[i] >= sum_weight)
            {
                return false;
            }
            else
            {
                sum_weight += fishes[i];
            }
        }
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
//    vector<pair<int, int>> fishes(n);
    vector<int> fishes(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> fishes[i];
//        fishes[i].ND = i;
    }
    vector<int> org_fishes = fishes;
    sort(fishes.rbegin(), fishes.rend());
    if(n > 1 && fishes.front() == fishes.back())
    {
        for (int i = 0; i < n; ++i)
        {
            cout << "N";
        }
        cout << endl;
    }
    else

    {
        int b = 0, e = n-1, s = (b+e)/2;
        while (b < e)
        {
            if (can_king(fishes[s], fishes))
            {
                b = s;
                s = (b + e + 1) / 2;
            } else
            {
                e = s - 1;
                s = (b + e) / 2;
            }
        }
        int min_weight = fishes[s];
        for (auto el : org_fishes)
        {
            cout << ((el >= min_weight) ? "T" : "N");
        }
        cout << endl;
    }

}