"Ta-po Jewelry Co." is a factory that manufactures jewelry necklaces. The factory buys gemstones from $$$N$$$ suppliers, labeled Supplier 1 through Supplier $$$N$$$. To make a jewelry necklace, the factory chooses a piece of gemstone each from Supplier $$$l$$$ through Supplier $$$r$$$ and puts them together into a necklace in the same order as the supplier labels. However, the factory is managed by the second-generation descendant who is not very knowledgeable at jewelry despite working in the business. Even if some suppliers do not sell real gemstones, the factory still buys from them, creating necklaces of poor quality. The second-generation descendant consults Prof. TOI and receives help from a jewelry expert from the Land of Joy. The expert cuts the necklaces created by the factory so that a consecutive segment containing only real gemstones remains, in such a way that it is the longest possible consecutive segment. After necklaces from all possible supplier ranges are cut, they calculate the total length of all the necklaces.
During the whole time the expert is hired, the factory creates a necklace for each possible supplier range from $$$l$$$ to $$$r$$$ for $$$1 \leq l \leq N$$$ and $$$l \leq r \leq N$$$ and sends it to the expert to cut.
For example, the factory buys from 5 suppliers, where Supplier 1 and Supplier 4 sells fake gemstones (denoted 'F') and all other suppliers sell real gemstones (denoted 'T'). In this case, the gemstones sold by Suppliers 1 through 5 can be written as the following string: $$$$$$\tt{FTTFT}$$$$$$ and after the factory creates a necklace for each supplier range $$$l$$$ to $$$r$$$ for $$$1 \leq l \leq 5$$$ and $$$l \leq r \leq 5$$$, the following necklaces are sent to be cut by the expert:
| necklace from supplier range $$$(l,r)$$$ | necklace after the expert cuts | obtained length | necklace from supplier range $$$(l,r)$$$ | necklace after the expert cuts | obtained length | |
| F (1,1) | - | 0 | TTFT (2,5) | TT | 2 | |
| FT (1,2) | T | 1 | T (3,3) | T | 1 | |
| FTT (1,3) | TT | 2 | TF (3,4) | T | 1 | |
| FTTF (1,4) | TT | 2 | TFT (3,5) | T | 1 | |
| FTTFT (1,5) | TT | 2 | F (4,4) | - | 0 | |
| T (2,2) | T | 1 | FT (4,5) | T | 1 | |
| TT (2,3) | TT | 2 | T (5,5) | T | 1 | |
| TTF (2,4) | TT | 2 |
Thus, the factory determines that the total length of all necklaces after the expert cuts them equals to $$$0 + 1 + 2 + 2 + 2 + 1 + 2 + 2 + 2 + 1 + 1 + 1 + 0 + 1 + 1 = 19$$$
Your Task
Write an efficient program to determine the total length of all necklaces after the expert cuts them.
There are 2 lines of input:
| Line 1 | Integer $$$N$$$ denotes the number of suppliers the factory buys from, where $$$1 \leq N \leq 1,000,000$$$ |
| Line 2 | String $$$S$$$ of length $$$N$$$ whose characters are all 'T' and 'F'. Let $$$S_i$$$ denote the character at position $$$i$$$. If $$$S_i$$$ equals 'T', then Supplier $$$i$$$ sells real gemstones, but if $$$S_i$$$ equals 'F' , then Supplier $$$i$$$ sells fake gemstones ($$$i = 1, ... , N$$$). |
There is 1 line of output:
| Line 1 | The total length of all necklaces after the expert cuts them. |
Notices regarding the test sets are as follows:
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 6 | $$$N \leq 300$$$ |
| 2 | 18 | $$$N \leq 5{,}000$$$ |
| 3 | 6 | The string $$$S$$$ is in the format FF...FFTT...TT (the string begins with a consecutive run of character F and ends with a consecutive run of character T) |
| 4 | 7 | The string $$$S$$$ is in the format FF...FFTT...TTFF...FF (the string begins and ends with a consecutive run of character F and the string contains a consecutive run of character T as a substring in the middle) |
| 5 | 8 | The string $$$S$$$ is in the format TT...TTFF...FFTT...TT (the string begins and ends with a consecutive run of character T and the string contains a consecutive run of character F as a substring in the middle) |
| 6 | 23 | None of the substrings of string $$$S$$$ is a consecutive run of character T or a consecutive run of character F with more than 100 characters |
| 7 | 32 | No additional constraints |
5 FTTFT
19
5 TTTTT
35
8 FFFTTTTT
80
Recommended programming tips
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
