题目描述

小$\text{Q}$和$\text{tangjz}$正在一个长度为$n$的序列$a_1,a_2,\ldots,a_n$上玩一个有趣的关于区间翻转的游戏。小$\text{Q}$和$\text{tangjz}$轮流行动，小Q先手。每次行动方玩家需要选择一个长度为$4x+2$或$4x+3$的区间$[l,r]$，其中$x$是该玩家自行选择的非负整数，然后将$a_l,a_{l+1},...,a_{r-1},a_r$翻转，例如$\text{1 3 2 5 4}$翻转会得到$\text{4 5 2 3 1}$。为了防止游戏无限进行下去，他们规定每次操作之后得到的新序列的字典序必须比操作前的序列大。最先不能采取任何行动的玩家将会输掉这局游戏。假设小$\text{Q}$和$\text{tangjz}$都会采取最优策略行动，请写一个程序判断谁会获得这局游戏的胜利。

输入格式

第一行包含一个正整数$n$，表示序列的长度。

第二行包含n个互不相同的正整数$a_1,a_2,...,a_n$，分别表示序列中的每个元素。

输出格式

输出一行一个字符，若小$\text{Q}$胜利，输出Q；若$\text{tangjz}$胜利，输出"T"（不含引号）。

样例

4
4 2 1 3

T

数据规模与约定

对于$100\%$的数据：$1\le n\le 50,1\le a_i\le n,1\le l\le r\le n$.