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

using namespace std;

int main()
{
    int n;
    cin>>n;

    vector<pair<int,int>> tab(n+1);

    tab[0].first=-1;
    tab[0].second=-1;

    for(int i=1;i<=n;i++)
    {
        cin>>tab[i].first;
        tab[i].second=i;
    }

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

    vector<long long> prefix(n+2);
    prefix[0]=0;

    vector<pair<int,int>> would_be_king(n+1);

    for(int i=1;i<=n;i++)
    {
        prefix[i]=prefix[i-1]+tab[i].first;
    }

    tab.push_back(make_pair(0,0));
    would_be_king.push_back(make_pair(n+1,1));
    would_be_king[0]=make_pair(0,0);

    for(int i=n;i>0;i--)
    {
        //cout<<tab[i].first<<endl;;
        //cout<<prefix[i]<<" "<<tab[i+1].first<<endl;

        if(prefix[i]>tab[i+1].first)
        {
            int x=would_be_king[i+1].second;

            would_be_king[i]=make_pair(tab[i].second,x);
        }
        else
        {
            would_be_king[i]=make_pair(tab[i].second,0);
        }
        
    }

    /*for(int i=0;i<would_be_king.size();i++)
    {
        cout<<would_be_king[i].first<<" "<<would_be_king[i].second<<endl;
    }*/

    int y=tab[would_be_king[1].first].first;

    int id=2;

    while (id<=n && tab[id].first==tab[1].first)
    {
        would_be_king[id].second=0;
        id++;
    }
    

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

    for(int i=1;i<=n;i++)
    {

        if(would_be_king[i].second==1)
        {
            cout<<"T";
        }
        else
        {
            cout<<"N";   
        }
        
    }

    cout<<endl;
    

    return 0;
}