哲学（philosophy）

题目背景

为什么……为什么你想要从我面前消失啊。 为什么，还要出现在我的面前； 为什么，同意我呆在你身边； 为什么，总是说些不清不楚的话； 为什么，总是摆着一副好像对我一点也不讨厌的态度； 为什么，没有来听我的钢琴； 为什么，不能接受我啊； 为什么你会这么熟练啊！你到底要把我甩开多远你才甘心啊！？ 在你观看老番时，『它』突然进来了，所以你决定开始写有限状态广义后缀自动机

题目描述

『她』和『他们』的关系太过复杂，简单来说就是 happy or sad。为了方便表示，我们可以用一个长度为 𝑛 的 hs 字符串 𝑆 来进行表示。 在『他们』眼里，一段好的关系必然是一个按字典序升序排序的字符串，即所有 ℎ 在前，𝑠 在后。 假如某一段的关系中，设 𝑐𝑛𝑡ℎ, 𝑐𝑛𝑡𝑠 分别表示该子段中字符 h 和字符 s 的数量。 那么可以花费 |𝑐𝑛𝑡ℎ − 𝑐𝑛𝑡𝑠| + 1 的代价将这段关系修复一段好的关系。 于是，『她』想要将『她』和『他们』的一段关系修复一段好的关系。 同样，修复关系不是一朝一夕可以完成的，所以我们允许，可以在修复关系时可以不断选择这段关系的子串变为一个好的关系。 例如，对于一段 hshssh，选择 2 ∼ 4 的子串花费 2 代价修复成 hhsssh。 现在，『她』在修复关系前，想要知道将这整段关系修复成好的关系的所需的最少代价。

输入格式

第一行一个正整数 𝑛，表示字符串的长度。 第二行一个字符串，长度为 𝑛。 由于本题输入量过大，选手可以使用下发文件中的代码进行输入。

输出格式

输出一行一个整数。

数据范围