Problem 1076 --妹妹的打印难题

1076: 妹妹的打印难题

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 84  Solved: 10
[Submit][Status][Web Board][Creator:]

Description

一天,妹妹请一位设计师利用"H"和"U"两种大写字母设计了一个字符串作为某场活动的宣传条幅,当妹妹去打印店印制条幅时得知,打印条幅统一收费20元钱,但由于"HHU"为世界某著名大学的简称,条幅内容中每出现一次"HHU"就需要额外交纳1元的版权费用。

妹妹希望能够尽可能少的付打印费,省下的钱可以用来买糖吃,因此她联系了设计师,设计师允许她每次删除字符串中的一个字符。但由于更改设计是一件很麻烦的事情,所以每次删除设计师都要收取一定的费用,第1次不收费,第2次收1元,.....,第i次删除收取(i-1)元。

由于妹妹的数学很差,希望能请你帮忙计算一下打印条幅最少需要交纳多少钱,并答应事成之后请你一起吃糖。

Input

本题有多组测试用例,请读到文件末尾(EOF),测试用例不超过200组。

第一行一个正整数N,表示字符串的长度。(1<=N<=1000000)

第二行为一个字符串S。题目保证S仅由大写字母"H"和"U"组成。

Output

在一行中输出一个正整数,代表打印该条幅总共需要的最少花费。

Sample Input

6
HHHUHH

Sample Output

20

HINT

妹妹必须要打印出该条幅,因此不能将设计的字符串中的字符全部删除。
ps:由于读入数据量较大,请使用scanf或cin关闭同步流的方式进行读入。

Source

[Submit][Status]