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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#ifdef _HOME_
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define RESULT(x) {cout<<(x);return 0;}

const int MAX_N = 500001;
int in[MAX_N];
int tab[MAX_N];
long long sum[MAX_N];
int n;

int getSmallestKing() {
	if (tab[0] == tab[n-1]) // all same size - noone can be king
		return 2000000000;
	//at least 2 different sizes - always at least 1 king
	int lastKing = n-1;
	for(int i=n-2;i>=0;--i) {
		while(i>=0 && tab[i+1]==tab[i])
			--i;
		if (i==-1 || tab[0]==tab[i]) {
			DEBUG(cerr<<"Stop - all except smallest can be king"<<endl;)
			break;
		}
		if ((long long)(tab[i]+sum[i]) <= tab[lastKing]) {
			DEBUG(cerr<<"Stop - fish "<<tab[i]<<" can be at max "<<tab[i]+sum[i]<<" < "<<tab[lastKing]<<endl;)
			break;
		}
		DEBUG(cerr<<tab[i]<<" can be king - "<<tab[i]+sum[i]<<">"<<tab[lastKing]<<endl;)
		lastKing = i;
	}
	return tab[lastKing];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>n;
	REP(x,n) {
		cin >> tab[x];
	}
	memcpy(in, tab, n*sizeof(int));
	DEBUG(
			REP(x,n)
				if (in[x] != tab[x]) {
					cerr << "ERROR at index ["<<x<<"] - expected "<<tab[x]<<", got "<<in[x] << endl;
					return 1;
				}
	)
	sort(tab, tab+n, std::less<int>());
	sum[0] = 0;
	REP(x,n-1)
		sum[x+1] = sum[x]+tab[x];
	DEBUG(
			REP(x,n)
				cerr << sum[x] << " ";
			cerr << endl;
	)
	int smallestKing = getSmallestKing();
	REP(x,n)
		cout << (in[x]<smallestKing ? "N" : "T");
	return 0;
}