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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

#define FAST  ios_base::sync_with_stdio(0) ;cin.tie(0);

typedef long long ll;

void przekierowanie()
{
#ifdef TEST
    freopen( "input.txt", "r", stdin );
    freopen( "output.txt", "w", stdout );
#endif
}

class sum_t
{
public:
    ll waga;
    ll kumulacja;
    char wynik;
    long pozycja;
};

int main()
{
    FAST
    przekierowanie();
    ll n;
    cin >> n;

    vector <sum_t> sumy( n );
    for( long x = 0; x <  n; x ++)
    {
        sumy[ x ].pozycja = x;
        cin >> sumy[ x ].waga;
    }
    for( long y = 0; y< n; y ++) sumy[ y ].wynik = 'X';
    sort( sumy.begin(), sumy.end(), [](sum_t s1, sum_t s2)
    {
        return s1.waga < s2.waga;
    });

    // sprawdzenie przypadku NNNNN

    if( sumy[ 0 ].waga == sumy[ n - 1].waga )
    {
        for( long a = 0; a < n; a ++) cout << 'N';
        cout << '\n';
        return 0;
    }
    sumy[ 0 ].kumulacja = sumy[ 0 ].wynik = 'N';


    long h = 0;
    while( h < n && sumy[ h ].waga == sumy[ h + 1 ]. waga )
    {
        sumy[ h + 1 ].wynik = 'N';
        h ++;
    }
    long index_pierwszych = h;

    ll kum_pom = sumy[ h ].waga * (h + 1);
    for( long a = 0 ; a <= h; a ++ ) sumy[ a ].kumulacja = kum_pom;

    for( long x = h + 1; x < n; x ++ )
        sumy[ x].kumulacja = sumy[ x ].waga + sumy[ x - 1  ].kumulacja;

     h++;
     while( h < n )
    {
        auto hpom = h;
        while( hpom < n - 1 && sumy[ hpom ].waga == sumy[ hpom + 1].waga ) hpom ++;
        ll waga_pom = sumy[ h ].waga * ( hpom - h + 1 );
        for( long x = h; x <= hpom; x ++ )
            sumy[ x ].kumulacja = waga_pom + sumy[ h - 1 ].kumulacja;
        h = hpom + 1;
    }

    long i = n - 1;
    sumy[ i ].wynik = 'T';
    while( i > 0 && sumy[ i ].waga == sumy[ i - 1 ].waga )
    {
        sumy[ i - 1].wynik = 'T';
        i --;
    }
    i --;
    while( i > 0 )
    {
        if( sumy[ i ].kumulacja <=  sumy[ i + 1 ].waga )
        {
            while( i >0 )
            {
                sumy[ i ].wynik = 'N';
                i --;
            }
        }
        else
        {
            if( i <= index_pierwszych )
            {
                i = 0;
                break;
            }
            sumy[ i ].wynik = 'T';
            while( i > 0 && sumy[ i ]. waga == sumy[ i - 1 ]. waga )
            {
                sumy[ i - 1].wynik = 'T';
                i --;
            }
        }
        i --;
    }
    sort( sumy.begin(), sumy.end(), [](sum_t s1, sum_t s2)
    {
        return s1.pozycja < s2.pozycja;
    });
    for( long a = 0; a < n; a ++) cout << sumy[ a ].wynik;
    cout << '\n';
    return 0;
}