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
#include <stdio.h>
#include <stdlib.h>

struct SUM {
  int poz;
  int w;
  int o;
};

struct SUM sum[500*1001];

int compare_poz(const void *arg1, const void *arg2) {
  return (((struct SUM *)arg1)->poz - ((struct SUM *)arg2)->poz);
}
int compare_w(const void *arg1, const void *arg2) {
  return (((struct SUM *)arg1)->w - ((struct SUM *)arg2)->w);
}

int n;

int is_king(int k) {
  long long int ws = sum[k].w;
  for(int i = 0; i < n; i++) {
    if(i == k) {
      continue;
    }
    if(sum[i].w >= ws) {
      return 0;
    }
    ws += sum[i].w;
  }
  sum[k].o = 1;
  return 1;
}

void bisect(int l, int r) {
  if( l > r) {
    return;
  }
  if(l == r) {
    if(r != n) { is_king(r); }
    return;
  }
  if (l+1 == r) {
    is_king(l);
    if(r != n) { is_king(r); }
    return;
  }
  int mid = l + (r-l) / 2;
  int king = is_king(mid);
  if(king == 0) {
    bisect(mid+1, r);
  } else {
    bisect(l, mid);
  }
}

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    sum[i].o = 0;
    sum[i].poz = i;
    scanf("%d", &(sum[i].w));
  }
  qsort(sum, n, sizeof(*sum), compare_w);
  bisect(0, n);

/*  for(int i = 0; i < n; i++) {
    is_king(i);
  }*/
  int o_current = 0;
  for(int i = 0; i < n; i++) {
    if(sum[i].o == 1) {
      o_current = 1;
    }
    sum[i].o = o_current;
  }

/*  int current_ws = sum[0].w;
  long long int equal_weight_sum = 0;
  long long int weight_sum = 0;
  for(int i = 0; i < n; i++) {
    if(sum[i] == sum[0].w) {
      equal_weight_sum
    }
  }*/

  qsort(sum, n, sizeof(*sum), compare_poz);
  for(int i = 0; i < n; i++) {
    if(sum[i].o == 1) {
      printf("T");
    } else {
      printf("N");
    }
  }
  return 0;
}