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

using namespace std;
#define LL long long
#define fi first
#define sc second
#define endl '\n'
// Michal Jagodzinski

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> Def(N);
    vector<pair<int, int>> Input(N); //Wartosc, index
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        Input[i] = make_pair(a, i);
        Def[i] = a;
    }
    sort(Input.begin(), Input.end());
    vector<pair<LL, int>> prefsum; // prefsuma, Wartosc
    int It = 0;
    for(int i = 0; i < N; i++){
        if(Input[i].fi != Input[It].fi){
            if(prefsum.size() == 0) prefsum.push_back(make_pair((LL)(i - It) * Input[It].fi, Input[It].fi));
            else prefsum.push_back(make_pair(prefsum[prefsum.size()-1].fi + (LL)(i - It) * Input[It].fi, Input[It].fi));
            It = i;
        }
    }
    if(prefsum.size() == 0) prefsum.push_back(make_pair((LL)(N - It) * Input[It].fi, Input[It].fi));
    else prefsum.push_back(make_pair(prefsum[prefsum.size() - 1].fi + (LL)(N - It) * Input[It].fi, Input[It].fi));
    vector<char> Result(N, 'Q');
    It = 1e9 + 7;
    int Sc = 0;
//    for(auto [x, y] : prefsum) cout << x << " " << y << endl;
//    cout << endl;
    
    for(int i = 1; i < prefsum.size(); i++){
    	int Lit = i;
    	if(i > Sc){
    		while(Lit < prefsum.size() - 1 && prefsum[Lit].fi > prefsum[Lit+1].sc){
    			Lit++;
			}
			if(Lit == prefsum.size() - 1) It = prefsum[i].sc;
			Sc = Lit;
		}
    }
    
    for(int i = 0; i < N; i++){
    	if(Def[i] >= It) cout << "T";
    	else cout << "N";
	}
    return 0;
}