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 <stdio.h>
#include <algorithm>

int a[500001], pos[500001];
long long int sumy[500001];
int n;

void czytaj(void)
{
  int i,x;
  long long int S;

  scanf("%d\n",&n);
  for(i=0;i<n;++i)
  {
	  scanf("%d",&x);
	  a[i]=x; pos[i]=x;
  }	  
 
  std::sort(pos,pos+n);
  
  S=0;
  for(i=0;i<n;++i)
  {
	  S+=pos[i];
	  sumy[i]=S;
  }	  
 
  return;
}


int sum(int p)  //sprawdza, czy sum na pozycji p moze byc krolem  (1 - tak, 0 - nie)
{
	int f,i,x;
	long long int W;
	
	f=1; W=sumy[p];
	i=p+1;
	while(i<n && W>pos[i])
    {   
        if(W>pos[i]) W=sumy[i];
		i++;
    }
	if(i<n) f=0;
	return f;
}



int main()
{
    int p,k,s,i;
	
	czytaj();

    p=0; k=n; 
    while(k-p>1)
    {
       s=(p+k)/2;
       if (sum(s)==0) p=s; else k=s;
    }
    if (sum(s)==1) s--; 
    
    for(i=0;i<n;++i)
      if(a[i]<=pos[s]) printf("N"); else printf("T");

    printf("\n");
	return 0;
}