マルバツスタンプ (Circle Cross Stamps)

JOI 君はマルスタンプ，バツスタンプ，マルバツスタンプの3種類のスタンプをそれぞれ \(0\) 個以上持っている．これらはマルやバツのマークを紙に印字することができるスタンプである．

マルスタンプを使うとマルが \(1\) つ印字され，バツスタンプを使うとバツが \(1\) つ印字される．マルバツスタンプを使うとマルとバツが横一列に \(1\) つずつ印字され，スタンプの向きを変えることで，マルの右にバツが来るようにも，バツの右にマルが来るようにも印字できる．

JOI 君は，持っているスタンプをそれぞれちょうど \(1\) 回ずつ適当な順番で使い，紙に横一列にマルとバツを印字した．印字されたマルとバツの列は文字列 \(S\) で表される．\(S\) は O と X から構成された長さ \(N\) の文字列であり，\(S_i = \) O ならば JOI 君が印字したマークのうち左から \(i\) 番目のものがマルであることを表し，\(S_i =\) X ならばそれがバツであることを表す (\(1 ≦ i ≦ N\))．

あなたは，JOI 君が持っているスタンプの個数は分からないが，JOI 君が印字したマルとバツの列は知っている．印字されたマルとバツの列から，JOI 君が持っているマルバツスタンプの個数としてあり得るもののうち最大値を求めよ．

• \(1 ≦ N ≦ 100000 (= 10^5)\)
• \(S\) は長さ \(N\) の文字列である．
• \(S\) の各文字は O か X である．

入力は以下の形式で標準入力から与えられる．

\(N\)
\(S\)

JOI 君が持っているマルバツスタンプの個数としてあり得るもののうち最大値を出力せよ．

JOI 2019 · JCIOI · CC BY-SA 4.0