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
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>    // std::sort
#include <iostream>    // std::sort

std::map<long, std::vector<int>> sizeToIndexes;
std::map<long, long long> sizeToSmallerOrEqualSize;
bool * result;
int n;


void solve() {
  auto currentIter = sizeToSmallerOrEqualSize.rbegin();
  long prevSize = currentIter->first;
  for (auto index: sizeToIndexes[currentIter->first]) {
    result[index] = true;
  }
  currentIter ++;
  while (currentIter->first != sizeToSmallerOrEqualSize.begin()->first) {
    if (sizeToSmallerOrEqualSize[currentIter->first] <= prevSize) {
      return;
    }
    for (auto index: sizeToIndexes[currentIter->first]) {
      result[index] = true;
    }
    prevSize = currentIter->first;
    currentIter ++;
  }
}
  // for (auto iter = sizeToSmallerOrEqualSize.rbegin(); iter != sizeToSmallerOrEqualSize.rend(); ++iter) {
  //   if (iter != sizeToSmallerOrEqualSize.begin()) {

  //   }
  // }

int main() {
  scanf("%d\n", &n);
  result = new bool[n];
  for (int i=0; i < n; i++) {
    result[i] = false;
    long a;
    scanf("%ld", &a);
    auto it = sizeToIndexes.find(a);
    if (it == sizeToIndexes.end()) {
      std::vector<int> indexes;
      indexes.push_back(i);
      sizeToIndexes.insert(std::make_pair(a, indexes));
    } else {
      it->second.push_back(i);
    }
  }

  // printf("size=%d\n", sizeToIndexes.size());
  // for ( const auto &myPair : sizeToIndexes ) {
  //     std::cout << myPair.first << ":";
  //     for (const auto &value : myPair.second) {
  //       std::cout << value << " ";
  //     }
  //     std::cout << std::endl;
  // }

  long long smallerOrEqualSize = 0L;
  for ( const auto &myPair : sizeToIndexes ) {
      smallerOrEqualSize += (long) myPair.second.size() * (long) myPair.first;
      sizeToSmallerOrEqualSize.insert(std::make_pair(myPair.first, smallerOrEqualSize));
  }

  // std::cout << " ---------------------- \n";
  // for ( const auto &myPair : sizeToSmallerOrEqualSize ) {
  //     std::cout << myPair.first << ":" << myPair.second << std::endl;
  // }
  if (sizeToSmallerOrEqualSize.size() > 1) {
   solve();
  }

  for (int i=0; i<n; i++) {
    printf(result[i] ? "T" : "N");
  }
  
  return 0;
}