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

using namespace std;

#define MAXN 500050

int input[MAXN];
long long sum[MAXN];
int can_eat_next[MAXN];

int main()
{
	int n;
	vector<int> v;
	cin >> n;
	//cout << "CZYTAMY DANE" << endl;
	for (int i = 0; i < n; i++) {
		cin >> input[i];
		v.push_back(input[i]);
	}
	//cout << "DANE PRZECZYTANE" << endl;
	sort(v.begin(), v.end());
	
	sum[0] = v[0];
	can_eat_next[0] = 0;

	for (int i = 1; i < n; ++i) {
		sum[i] = sum[i-1] + v[i];
	}
	
	//cout << "WYLICZAMY CAN EAT NEXT" << endl;
	for (int i = 1; i < n-1; ++i) {
		if (v[i] == v[i-1] && can_eat_next[i-1] == 0) can_eat_next[i] = 0;
		else if (sum[i] > v[i+1]) can_eat_next[i] = 1;
	}
	if (v[n-1] > v[n-2]) can_eat_next[n-1] = 1;
	else can_eat_next[n-1] = can_eat_next[n-2];

	//cout << "WYLICZAMY MAX NIENAPIERDALAJACA" << endl;
	int max_niespierdalajaca = 2147483647;
	for (int i = n-1; i > 0; --i) {
		if (can_eat_next[i] == 1) max_niespierdalajaca = v[i];
		else break;
	}
	
	//for (int i = 0; i < n; ++i) {
	//	cout << v[i] << " ";
	//}
	//cout << endl << "A====================================" << endl;
	//	for (int i = 0; i < n; ++i) {
	//	cout << a[i] << " ";
	//}
	//cout << endl << "====================================" << endl;
	
	
	//cout << endl << "SUM====================================" << endl;
	//	for (int i = 0; i < n; ++i) {
	//	cout << sum[i] << " ";
	//}
	//cout << endl << "====================================" << endl;
	
	//cout << endl << "CAN====================================" << endl;
	//	for (int i = 0; i < n; ++i) {
	//	cout << can_eat_next[i] << " ";
	//}
	//cout << endl << "====================================" << endl;
	
	for (int i = 0; i < n; ++i) {
		if (input[i] >= max_niespierdalajaca) cout << 'T'; else cout << 'N';
	}
	cout << endl;
	
}