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

using namespace std;

struct S : pair<int, int> {
	S(int w, int idx) : pair<int,int>{w, idx}, maxw{w}, sum{w} {}
	S() {}
	int w() { return first; }
	int idx() { return second; }

	bool king{true};
	long long maxw;
	long long sum;
};

struct Sorter {
	Sorter(const vector<S> &v_) : v(v_) {}

	const vector<S> &v;

	bool operator()(int lhs, int rhs) {
		return v[lhs].first < v[rhs].first;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<S> v;
	v.reserve(N);
	vector<int> vi;
	vi.reserve(N);

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(S{a, i});
		vi.push_back(i);
	}
	sort(vi.begin(), vi.end(), Sorter(v));

	v[vi[0]].king = false;
	for (int i = 1; i < N; i++) {
		if (v[vi[i]].w() > v[vi[i-1]].w() || (v[vi[i]].w() == v[vi[i-1]].w() && v[vi[i-1]].maxw > v[vi[i-1]].w())) {
			v[vi[i]].maxw += v[vi[i-1]].sum;
		}
		v[vi[i]].sum += v[vi[i-1]].sum;
	}

	S &last = v[vi[N-1]];
	S &second_to_last = v[vi[N-2]];
	bool still = last.maxw > second_to_last.w();
	for (int i = N-1; i > 0; i--) {
		v[vi[i]].king = still;
		if (v[vi[i-1]].maxw <= v[vi[i]].w())
			still = false;
	}
	string vc;
	vc.resize(N, 'T');
	for (auto &i: v)
		if (!i.king) vc[i.idx()] = 'N';

	cout << vc << endl;

	return 0;
}