## DMOPC '18 Contest 3 P3 - Bob and Math Class

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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 questions. His answers are a string of 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?

#### Input Specification

The first line contains a single integer, .
The next line contains a string of 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 suspicious subarrays are

T
F
T
F
F
TF
FT
TF
FF
TFF
FTFF

#### Sample Input 2

5
TFTFT

#### Sample Output 2

9