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

struct Wels
{
    int id;
    int mass;
    char king;
    bool operator<(const Wels &rhs) { return mass < rhs.mass; }
};
std::ostream &operator<<(std::ostream &o, const Wels &w)
{
    return o << "Wels(id=" << w.id << ",mass=" << w.mass << ",king=" << w.king << ")";
}

void dump(const std::vector<Wels> &wels)
{
    for (const Wels&w : wels)
    {
        std::cout << w << std::endl;
    }
}

void output(std::vector<Wels> &wels)
{
    int n = wels.size();
    for (int i = 0; i < n; ++i)
    {
        while (wels[i].id != i)
        {
            int j = wels[i].id;
            std::swap(wels[i], wels[j]);
        }
    }
    for (Wels &w : wels)
    {
        std::cout << w.king;
    }
    std::cout << std::endl;
}

int main()
{
    using namespace std;
    int n;
    cin >> n;
    vector<Wels> wels(n);

    for (int i = 0; i < n; ++i)
    {
        wels[i].id = i;
        cin >> wels[i].mass;
    }

    sort(wels.begin(), wels.end());

    wels[0].king = 'N';

    int how_many_smallest = n;
    for (int i = 1; i < n; ++i)
    {
        if (wels[i].mass > wels[i - 1].mass)
        {
            how_many_smallest = i;
            break;
        }
        else
        {
            wels[i].king = 'N';
        }
    }

    if (how_many_smallest == n)
    {
        output(wels);
        return 0;
    }

    long long total_mass = how_many_smallest * wels[0].mass;
    int loser = how_many_smallest - 1;
    for (int i = how_many_smallest; i < n-1; ++i)
    {
        total_mass += wels[i].mass;
        if (total_mass <= wels[i+1].mass)
        {
            loser = i;
        }
    }
    for (int i = loser; i >= how_many_smallest; --i)
    {
        wels[i].king = 'N';
    }
    for (int i = loser+1; i < n; ++i)
    {
        wels[i].king = 'T';
    }

    output(wels);
    return 0;
}