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
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>

#define ll long long

using namespace std;

int n;
ll a[500005];
char res[500005];

void solve() {
  if(n == 1) {
    res[0] = 'T';
    return;
  }
  map<ll, int> cm;
  ll mx = 0;
  for(int i=0;i<n;i++) {
    cm[a[i]]++;
    mx = max(mx, a[i]);
  }
  map<ll, ll> toS;
  ll total = 0;
  for(auto it = cm.begin();it!=cm.end();it++) {
    total += (it->first) * (it->second);
    toS[it->first] = total;
    if(total > mx) {
      break;
    }
  }
  set<ll> z;
  for(auto it = cm.begin();it!=cm.end();it++) {
    ll cur = it->first;
    ll eaten = 0;
    ll lastEat = -1;
    while(cur <= mx) {
      auto lo = toS.lower_bound(cur);
      if(lo == toS.begin()) {
        break;
      }
      lo--;
      if(lo->first <= lastEat) {
        break;
      }
      ll toEat = lo->second;
      lastEat = lo->first;
      if(lastEat >= it->first) {
        toEat -= it->first;
      }
      cur += toEat - eaten;
      eaten = toEat;
    }
    if(cur > mx) {
      z.insert(it->first);
    }
  }
  for(int i=0;i<n;i++) {
    res[i] = (z.find(a[i]) != z.end())?'T':'N';
  }
}

int main(int argc, char** argv) {
  scanf("%d", &n);
  for(int i=0;i<n;i++) {
    scanf("%lld", &(a[i]));
  }
  solve();
  res[n] = '\0';
  printf("%s\n", res);
  return 0;
}