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
//Mateusz Piórkowski
#include <iostream>
#include <vector>
#include <algorithm>

//#define DEBUG

struct fish{
	uint64_t id;
	uint64_t mass;
	uint64_t mass_after_eating_smaller;
	uint64_t same_size;
};

/*bool operator<(const fish &a, const fish &b)
{
	return a.mass < b.mass;
}*/
struct fish_compare
{
    inline bool operator() (const fish& a, const fish& b)
    {
		return a.mass < b.mass;
    }
};

//bool check_if_king(std::vector<fish>& fish_list, uint64_t pos){
//	uint64_t current_mass=0;
//	for(uint64_t i=pos; i<fish_list.size(); i++){
//		
//	}
//}

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

	uint64_t n;
	std::cin >> n;
	std::vector<fish> fish_list;
	bool *can_become_king = new bool[n];
	for(uint64_t i=0; i<n; i++){
		can_become_king[i]=false;
		uint64_t mass;
		std::cin >> mass;
		fish_list.push_back({i, mass, 0, 0});
	}
	std::sort(fish_list.begin(), fish_list.end(), fish_compare());

	uint64_t current_mass=0;
	uint64_t prev_mass=0;
	uint64_t mass_to_add_later=0;
	uint64_t same_size=0;
	for(auto it=fish_list.begin(); it!=fish_list.end(); ++it){
		if(prev_mass==it->mass){ //Same mass so can't eat
			mass_to_add_later+=it->mass;
			same_size++;
		}else{
			current_mass+=mass_to_add_later;
			current_mass+=it->mass;
			mass_to_add_later=0;
			same_size=0;
		}
		prev_mass=it->mass;
		it->mass_after_eating_smaller = current_mass;
		it->same_size = same_size;
		#ifdef DEBUG
		std::cout << "["<<it->id<<"] " << it->mass;
		std::cout << " current_mass:" << current_mass;
		std::cout << " mass_to_add_later:" << mass_to_add_later;
		std::cout << " same_size:" << it->same_size;
		std::cout << std::endl;
		#endif
	}
	//Solve
	uint64_t previous_mass=0;
	for(uint64_t i=0; i<fish_list.size(); i++){
		uint64_t current_mass=fish_list[i].mass_after_eating_smaller;
		uint64_t j;
		if(fish_list[i].mass==previous_mass){
			continue;
		}
		previous_mass=fish_list[i].mass;
		for(j=i+1; j<fish_list.size(); j++){
			if(current_mass>fish_list[j].mass){ //Can eat
				current_mass+=fish_list[j].mass;
			}else{ //Can't eat
				i=j-1; //Continue from fish j
				break;
			}
		}
		if(j==fish_list.size()){ //Ate all
			for(uint64_t j=i; j<fish_list.size(); j++){
				can_become_king[fish_list[j].id] = true; //All bigger fish can also become kings
				i=fish_list.size();
			}
		}
	}

	for(uint64_t i=0; i<n; i++){
		if(can_become_king[i]){
			std::cout << "T";
		}else{
			std::cout << "N";
		}
	}
	std::cout << "\n";
	delete[] can_become_king;
}