Title
Problem Statement
We have a string X, which has an even number of characters. Half the characters are S
, and the other half are T
.
Takahashi, who hates the string ST
, will perform the following operation 1010000 times:
- Among the occurrences of
ST
in X as (contiguous) substrings, remove the leftmost one. If there is no occurrence, do nothing.
Find the eventual length of X.
Constraints
- 2 ≦ |X| ≦ 200,000
- The length of X is even.
- Half the characters in X are
S
, and the other half are T
.
Partial Scores
- In test cases worth 200 points, |X| ≦ 200.
Input
The input is given from Standard Input in the following format:
X
Output
Print the eventual length of X.
Sample Input 1
TSTTSS
Sample Output 1
4
In the 1-st operation, the 2-nd and 3-rd characters of TSTTSS
are removed.
X becomes TTSS
, and since it does not contain ST
anymore, nothing is done in the remaining 1010000-1 operations.
Thus, the answer is 4.
Sample Input 2
SSTTST
Sample Output 2
0
X will eventually become an empty string: SSTTST
⇒ STST
⇒ ST
⇒ ``.
Sample Input 3
TSSTTTSS
Sample Output 3
4
X will become: TSSTTTSS
⇒ TSTTSS
⇒ TTSS
.