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~ Ts and 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 TTTT while TFTTTFT is not suspicious. Given Bob's answers, how many of its subarrays are suspicious?

Constraints

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~

Input Specification

The first line contains a single integer, ~N~.
The next line contains a string of ~N~ characters, either T or F.

Output Specification

Output a single integer, the number of suspicious subarrays.

Sample Input 1

5
TFTFF

Sample Output 1

11

Explanation of Sample 1

The ~11~ suspicious subarrays are

T
 F
  T
   F
    F
TF
 FT
  TF
   FF
  TFF
 FTFF

Sample Input 2

5
TFTFT

Sample Output 2

9