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


using namespace std;
#define LL long long

#define DBG(X) X

bool canEatAll(const vector<pair<int, int> > &counts, int idx)
{
    LL s = counts[idx].first;
    for (int i=idx+1; i < counts.size(); i++)
    {
        s += counts[i].first * counts[i].second;
    }
    if (s <= counts[idx].first) return false;
    s += 1LL * counts[idx].first * (counts[idx].second - 1);
    LL maxPossible = counts[0].first;
    for (int j=idx-1; j>=0; j--)
    {
        if (s > maxPossible) return true; // early exit
        if (s > counts[j].first)
        {
            s += 1LL * counts[j].first * counts[j].second;
        }
        else 
        {
            break;
        }
    }
    return s > maxPossible;
}

int binarySearch(const vector<pair<int, int> > &counts)
{
    int L = 0;
    int R = counts.size() -1;
    int ans = -1;
    while (L <= R)
    {
        int mid = L + (R-L)/2;
        if (!canEatAll(counts, mid))
        {
            ans = mid;
            R = mid - 1;
        }
        else 
        {
            L = mid+1;
        }
    }

    return ans;
}


void solve(vector<int> &a, vector<bool> &solution)
{
    int n = a.size();
    map<int, vector<int> > locations;
    for (int i=0; i < n; i++)
    {
        int x = a[i];
        if (locations.find(x) == locations.end())
        {
            locations[x] = vector<int>();
        }
        locations[x].push_back(i);
    }
    sort(a.begin(), a.end()); reverse(a.begin(), a.end());
    vector<pair<int, int> > counts;
    counts.push_back(make_pair(a[0], 1));
    for (int i=1; i < n; i++)
    {
        if (a[i] != counts.back().first) {
            counts.push_back(make_pair(a[i], 0));
        }
        counts.back().second++;
    }
    /*for (auto &x : counts) {
        printf("(%d,%d)", x.first, x.second);
    }*/
    int firstNonKing = binarySearch(counts);
    //printf("firstNonKing=%d at idx=%d\n", counts[firstNonKing].first, firstNonKing);
    for (int i=0; i < firstNonKing; i++)
    {
        vector<int> pos = locations[counts[i].first];
        for (int x : pos) {
            solution[x] = true;
        }
    }
    return;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i=0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    vector<bool> solution(n, false);
    solve(a, solution);
    for (int i=0; i < n; i++)
    {
        printf(solution[i] ? "T" : "N");
    }
    printf("\n");
}