Bob has a pop quiz in math! Fortunately, it's only a true and false quiz. He has already finished and is checking over his answers to the ~N~ questions. His answers are a string of ~N~
Fs. Bob calls an array suspicious if it contains a subarray of only
Ts or only
Fs such that the length of the subarray is at least half of the length of the entire array. For example,
TTTTFTF is a suspicious subarray since it contains
TFTTTFT is not suspicious. Given Bob's answers, how many of its subarrays are suspicious?
Subtask 1 [10%]
~1\le N\le 400~
Subtask 2 [30%]
~1\le N\le 2\,000~
Subtask 3 [40%]
~1\le N\le 200\,000~
Subtask 4 [20%]
~1\le N\le 1\,000\,000~
The first line contains a single integer, ~N~.
The next line contains a string of ~N~ characters, either
Output a single integer, the number of suspicious subarrays.
Sample Input 1
Sample Output 1
Explanation of Sample 1
The ~11~ suspicious subarrays are
T F T F F TF FT TF FF TFF FTFF
Sample Input 2
Sample Output 2