题目描述

给定一个字符串 $X$。$X$ 的长度为偶数，其中一半字符为 S，另一半为 T。

高桥君不喜欢字符串 ST。因此，他决定进行 $10^{10000}$ 次如下操作：

• 从 $X$ 的（连续的）子串中，找到最左边的 ST 并将其移除。如果不存在，则什么也不做。

请你求出最终 $X$ 剩下的字符数。

输入格式

输入从标准输入中给出，格式如下：

$X$

输出格式

输出一行，表示问题的答案。

样例 1

输入

TSTTSS

输出

4

样例 2

输入

SSTTST

输出

0

样例 3

输入

TSSTTTSS

输出

4

说明/提示

限制条件

• $2 \leq |X| \leq 200,\!000$
• $X$ 的长度为偶数
• $X$ 中一半字符为 S，另一半为 T

部分分

• 对于 $200$ 分的数据，$|X| \leq 200$

样例解释 1

第一次操作时，TSTTSS 的第 $2,3$ 个字符是 ST，将其移除。$X$ 变为 TTSS，此时已没有 ST，剩下 $10^{10000}-1$ 次操作都不做。因此答案为 $4$。

样例解释 2

SSTTST ⇒ STST ⇒ ST ⇒ ``，最终变为空字符串。

样例解释 3

TSSTTTSS ⇒ TSTTSS ⇒ TTSS。

由 ChatGPT 4.1 翻译