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

struct Rownowaznicy {
	int liczba;
	int64_t zasieg;
	bool krol = false;
};

int main()
{
	std::vector<int> morze;
	std::map<int, Rownowaznicy> sumy;
	int sumow;

	std::cin >> sumow;

	morze.reserve(sumow);

	for (int i = 0; i < sumow; ++i) {
		int masa;
		std::cin >> masa;
		morze.push_back(masa);
		auto rownowaznicy = sumy.find(masa);
		if (rownowaznicy == sumy.end()) {
			sumy.insert({masa, Rownowaznicy{1, masa}});
		} else {
			sumy[masa].liczba++;
		}
	}

	if (sumy.size() == 1) {
		if (sumy.begin()->second.liczba == 1) {
			std::cout << "T" << std::endl;
		} else {
			std::cout << std::string(sumy.begin()->second.liczba, 'N') << std::endl;
		}
		return 0;
	}

	for (auto sum = sumy.begin();; ++sum) {
		int64_t zasieg_poprzedniego = 0;
		if (sum != sumy.begin()) {
			zasieg_poprzedniego = (--sum)->second.zasieg;
			++sum;
		}
		sum->second.zasieg = int64_t(sum->first) * sum->second.liczba + zasieg_poprzedniego;
		if (sum == sumy.end()) {
			break;
		}
	}
	sumy.begin()->second.zasieg = sumy.begin()->first;

	sumy.rbegin()->second.krol = true;
	for (auto sum = ++sumy.rbegin(); sum != sumy.rend(); ++sum) {
		auto poprzedni = --sum;
		++sum;
		if (!poprzedni->second.krol) {
			break;
		}
		sum->second.krol = poprzedni->second.krol && poprzedni->first < sum->second.zasieg;
	}

	for (int masa : morze) {
		std::cout << ("NT"[sumy[masa].krol]);
	}
	std::cout << std::endl;
	return 0;
}