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
#include <algorithm>
#include <iostream>
using namespace std;

#define N 500000
#define A 1000000000

struct num {
  unsigned a;
  unsigned cumsum;
  int idx;
  bool king;
};

num nums[N + 1];
bool out[N + 1];

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  unsigned a, mina, maxa;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a;
    nums[i] = {.a = a, .idx = i, .king = false};
  }
  sort(nums, nums + n, [](num a, num b) { return a.a < b.a; });
  mina = nums[0].a;
  maxa = nums[n - 1].a;

  nums[0].cumsum = nums[0].a;
  for (int i = 1; i < n; i++) {
    nums[i].cumsum = min(maxa + 1, nums[i].a + nums[i - 1].cumsum);
  }

  nums[n - 1].king = nums[n - 1].a > mina;
  for (int i = n - 2; i >= 0 && nums[i + 1].king && nums[i].a > mina; i--) {
    nums[i].king = nums[i].cumsum > nums[i + 1].a;
  }

  for (int i = 0; i < n; i++) {
    out[nums[i].idx] = nums[i].king;
  }
  for (int i = 0; i < n; i++) {
    cout << (out[i] ? 'T' : 'N');
  }
  cout << endl;

  return 0;
}