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

using namespace std;
typedef long long ll;

const int rozmiar = 5e5 + 5;
ll tab[3][rozmiar]; // wartosc, max(value),value-index

int oryginal_t[rozmiar];
int n;
string wynik = "";
ll sumy_pre[rozmiar];

char bs(int x)
{
    int l = 1;
    int p = n;
    int s;

    // cout << "X: " << x << "\n";

    while (l <= p)
    {
        s = (l + p) / 2;
        if (tab[0][s] > x) p = s - 1;
        else if (tab[0][s] < x) l = s + 1;
        else
        {
            if (tab[2][s] == n)
                return 'T';
            return 'N';
        }
        //cout << "S: " << s << "\n";
    }
    return '0';
}

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

    
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> tab[0][i];
        oryginal_t[i] = tab[0][i];
    }

    sort(tab[0] + 1, tab[0] + n + 1);
    for (int i = 1; i <= n; i++)
    {
        sumy_pre[i] = sumy_pre[i - 1] + tab[0][i];
    }

    for (int i = 1; i <= n; i++)
    {
        if (tab[2][i - 1] >= i)
        {
            tab[1][i] = tab[1][i - 1];
            tab[2][i] = tab[2][i - 1];
        }
        else if (tab[0][i] == tab[0][i - 1])
        {
            tab[1][i] = tab[1][i - 1];
            tab[2][i] = tab[2][i - 1];
        }
        else
        {
            //tab[1][i] = tab[1][i - 1] + tab[0][i];
            tab[1][i] = sumy_pre[i];
            tab[2][i] = i;
            int j = i + 1;
            while (j <= n && tab[1][i] > tab[0][j])
            {
                tab[1][i] += tab[0][j];
                tab[2][i] = j;
                ++j;
            }
        }
    }

    //cout << tab[2][1] << "\n";

    //cout << bs(oryginal_t[2]);

    for (int i = 1; i <= n; i++)
    {
        wynik += bs(oryginal_t[i]);
    }

    cout << wynik << "\n";

    return 0;
}