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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>

// #define DEBUG_M
#ifdef DEBUG_M
#define DEBUGF(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG(expr) expr
#else
#define DEBUGF(...)
#define DEBUG(expr)
#endif

using namespace std;

typedef int64_t i64;

struct fish {
	i64 value;
	i64 prefix;
};

i64 minElem; // GLOBAL

bool operator<(const fish& a, const fish& b) {
	return (a.value != b.value) ? a.value < b.value : a.prefix < b.prefix;
}

bool is_possible(i64 size, const vector<fish> &fishes /* 100% valid english :) */) {
	i64 maxSize = fishes[fishes.size()-2].prefix;

	DEBUGF("initial size: %d; minElem: %d;\n", (int) size, (int) minElem);
	if (size++ == minElem) {
		return false;
	}

	for (;size < maxSize;) {
		fish fakeFish = {size, -1};
		auto newSizeIter = lower_bound(fishes.begin(), fishes.end(), fakeFish);

		newSizeIter--;
		
		i64 newSize = newSizeIter -> prefix;
		DEBUGF("new size: %d\n", (int) newSize);
		if (newSize >= maxSize) {
			DEBUGF("returning true\n");
			return true;
		}	else if (newSize == size) { // Nothing changed
			DEBUGF("returning false\n");			
			return false;
		} else { // newSize > size
			size = newSize;
		}
	}

	return true; // Should never happen as well
}

bool is_possible_linear(int idx, const vector<fish> &fishes /* 100% valid english :) */) {

	DEBUGF("initial idx: %d; initial val: %d;\n", idx, (int) fishes[idx].value);

	if (fishes[idx].value == minElem) {
		return false;
	}
	
	for (int i = idx+1; i < fishes.size()-1; i++) {
		if (fishes[i-1].prefix <= fishes[i].value)
			return false;
	}

	return true;
}


int main() {
	int n;
	scanf(" %d", &n);
	std::vector<int> inFish(n);
	std::vector<fish> sortFish(n+1, {0,0});

	for (int i = 0; i < n; i++) {
		scanf(" %d", &inFish[i]);
		sortFish[i].value = inFish[i];
	}

	if (n == 1) {
		puts("T");
		return 0;
	}
	
	sortFish[n] = {1000000001, 1LL << 48};
	std::sort(sortFish.begin(), sortFish.end());

	minElem = sortFish[0].value;
	sortFish[0].prefix = sortFish[0].value;
	for (int i = 1; i < n; i++) {
		sortFish[i].prefix = sortFish[i-1].prefix + sortFish[i].value;
	}

	int down = 0;
	int up = n+1;
	/* int lastDown = 0;
	int lastUp = 0;
	bool lastDownRes = false;
	bool lastUpRes = false; */
	
	for (;down < up;) {
		int mid = (down+up)/2;
		// int val = sortFish[mid].value;
		bool res;
		
		/* if (lastDown == val) {
			res = lastRes;
		} else if (lastUp == val) {
			
		} else { */

		// res = is_possible(val, sortFish);
		res = is_possible_linear(mid, sortFish);

		if (res) {
			up = mid;
		} else {
			down = mid + 1;
		}
		// lastVal = val;
		// lastRes = res;		
	}
	int limit = (int) sortFish[down].value;
	DEBUGF("down: %d; val[down]: %d;\n", down, (int) sortFish[down].value);
	for (int weight : inFish) {
		putchar(weight >= limit ? 'T': 'N');
	}
	puts("");
}