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
#include <stdio.h>
#include <bits/stdc++.h>

typedef long long ll;
ll Weights[1000000];
ll Indexes[1000000];
ll PrefSum[1000000];
bool CanEat[1000000];

int main() {
	int n;
	scanf("%d ", &n);
	for(int i=0; i<n; i++) {
		scanf("%lld ", &Weights[i]);
		Indexes[i] = i;
	}
	std::sort(&Indexes[0], &Indexes[n], [&](int i,int j){return Weights[i]<Weights[j];} );
	ll sum = 0;
	for(int i=0; i<n; i++) {
		int idx = Indexes[i];
		sum += Weights[idx];
		PrefSum[idx] = sum;
	}
	ll min = Weights[Indexes[0]];
	ll max = Weights[Indexes[n-1]];

	for(int i=n-1; i >= 0; i--) {
		int idx = Indexes[i];

		if(Weights[idx] == min)
			break;
		if(i == n - 1 && max != min) {
			CanEat[idx] = true;
			continue;
		}

		int nextIdx = Indexes[i+1];//idx + 1;
		if(PrefSum[idx] > Weights[nextIdx]){
			CanEat[idx] = true;
			continue;
		}
		break;
	}
	for(int i=0; i < n; i++) {
		printf("%c", CanEat[i] ? 'T' : 'N');
	}
	printf("\n");
	return 0;
}