正/邪
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}现有 n 名英雄排成一排,每名英雄的属性要么是正义,要么是邪恶。
\hspace{15pt}你可以进行无限次的合成操作,每一次操作的过程如下:
\hspace{23pt}\bullet\,选择任意名连续的站在一起的英雄;
\hspace{23pt}\bullet\,选择的英雄中,如果恰有奇数名邪恶英雄,会合成得到一名邪恶英雄,否则会合成得到一名正义英雄;
\hspace{23pt}\bullet\,合成后,原英雄全部消失,新英雄出现在消失的第一位原英雄的位置上;消失的英雄的左右剩余英雄将拼接形成新的一个队伍,下一步的操作基于新队伍进行。
\hspace{15pt}在可以进行无限次合成操作的前提下,最多能留下多少名正义英雄?

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(3 \le n \le 10^6\right) 代表初始队列中的英雄数量。
\hspace{15pt}第二行输入一个长度为 n,仅由字母 \texttt{`y'}\texttt{`n'} 组成的字符串 s 代表初始队列中的英雄属性。其中,s_i=\texttt{`y'} 代表第 i 名英雄是正义英雄,s_i=\texttt{`n'} 代表第 i 名英雄是邪恶英雄。

输出描述:

\hspace{15pt}输出一个整数,代表最多能留下的正义英雄的数量。
示例1

输入

复制
5
yyynn

输出

复制
4

说明

\hspace{15pt}在这个样例中,连续的选择第四和第五名英雄,因为他们都是邪恶英雄,所以会合成得到一名正义英雄。