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

時間制限 2 秒 / メモリ制限 256 MB / 得点 80 / x 20 /

TLE
2sec
MLE
256MB
得点
80

2018.12.11 15:50 補足説明を追加しました。

問題文

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 である．('O' と 'X' はそれぞれ、'O'(オー)と'X'(エックス)である.)

入力・出力

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

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

入出力例

入力例 1

5
OXXOX

出力例 1

2

JOI 君が印字したマークは，左から順に，マル，バツ，バツ，マル，バツである．JOI 君がマルスタンプ，バツスタンプ，マルバツスタンプをそれぞれ 0, 1, 2 個持っているとすると，以下の順番でスタンプを使えば，そのようにマークを印字することができる．

  • 1 つ目のマルバツスタンプを使ってマルとバツをこの順に印字する．
  • この右に，2 つ目のマルバツスタンプを使ってバツとマルをこの順に印字する．
  • 最後に，この右に，バツスタンプを使ってバツを印字する．

マルバツスタンプを 3 個以上持っているケースは考えられないので，2 を出力する．

入力例 2

14
OXOXOXOXXOXOXO

出力例 2

7

入力例 3

10
OOOOOOOOOO

出力例 3

0