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
#include <bits/stdc++.h>
using namespace std;

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

    long long n; cin >> n;

    vector<pair<long long, long long>> RybaIndeks(n);
    for(long long i = 0; i < n; i++)
    {
        cin >> RybaIndeks[i].first;
        RybaIndeks[i].second = i;
    }

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

    vector<pair<long long, long long>> WagaIlosc;
    vector<vector<long long>> Indeksy;

    long long akt_waga = RybaIndeks[0].first;
    long long akt_ilosc = 0;
    Indeksy.push_back({});


    for(auto p : RybaIndeks)
    {
        if(p.first == akt_waga)
        {
            akt_ilosc++;
            Indeksy.back().push_back(p.second);
        }
        else
        {
            Indeksy.push_back({});
            WagaIlosc.push_back({akt_waga, akt_ilosc});
            akt_waga = p.first;
            akt_ilosc = 1;
            Indeksy.back().push_back(p.second);
        }
    }

    WagaIlosc.push_back({akt_waga, akt_ilosc});

    if(WagaIlosc.size() == 1)
    {
        if(WagaIlosc[0].second == 1)
        {
            cout << 'T';
            return 0;
        }
        else
        {
            for(long long i = 1; i <= WagaIlosc[0].second; i++)
                cout << 'N';
            return 0;
        }
    }

    vector<long long> Maks(WagaIlosc.size());
    Maks[0] = WagaIlosc[0].first * WagaIlosc[0].second;
    for(long long i = 1; i < WagaIlosc.size(); i++)
    {
        Maks[i] = Maks[i - 1];
        Maks[i] += WagaIlosc[i].first * WagaIlosc[i].second;
    }
    Maks[0] = WagaIlosc[0].first;

    vector<long long> Jest(n);
    for(auto i : Indeksy.back())
        Jest[i] = true;

    for(long long i = WagaIlosc.size() - 2; i >= 0; i--)
    {
        if(Maks[i] > WagaIlosc[i + 1].first)
        {
            for(auto j : Indeksy[i])
                Jest[j] = true;
        }
        else
            break;
    }

    for(auto i : Jest)
        if(i)
            cout << 'T';
        else
            cout << 'N';

    return 0;
}