004 - 電飾

問題

JOI高校の文化祭では毎年廊下に電飾が飾られる．電飾は N 個の電球で構成されており，電球は廊下の 西側から東側に一列に並んでいる．各電球は明かりがついているか，ついていないかのいずれかの状態である．

JOI高校の倉庫には電球を操作する機械が眠っている．この機械は電飾内で連続した電球を指定すると， 指定された電球のうち，明かりがついている電球全てを明かりがついていない状態にし，明かりがついて いない電球全てを明かりがついている状態にする．ただし，機械は老朽化のため，1 回しか使用できない．

JOI高校の生徒達は明かりがついている電球とついていない電球が交互に並んだ列（このような電球の 列を交互列と呼ぶ）が好きである．そこで，この機械を必要ならば 1 回だけ使って，できるだけ長い交互 列を含む電飾を作ることにした．

例

例えば，電飾の配置が西から東に向かって

○○●●○●○○○●

となっていたとする（○は明かりがついている電球を，●は明かりがついていない電球を表す）．このとき， 4 番目から 7 番目までの4個の電球に対して機械を操作すると，

○○●○●○●○○●

となり，2 番目から 8 番目までの電球が長さ 7 の交互列をなす．

○○●○●○●○○●

また，8 番目の電球のみに対して機械を操作すると，

○○●●○●○●○●

となり，4 番目から 10 番目までの電球が長さ 7 の交互列をなす．

○○●●○●○●○●

機械を最大 1 回使用することで，長さが 8 以上の交互列を作ることはできない．

課題

電飾の情報が与えられたとき，機械を最大 1 回使用することで得られる電球の配列に含まれる交互列の 長さとして考えられるものの最大値を求めるプログラムを作成せよ．

制限

2 ≤ N ≤ 100,000 電飾を構成する電球の個数

入力

標準入力から以下のデータを読み込め．

• 1 行目には整数 N が書かれている．
• 2 行目には N 個の0または1が空白を区切りとして書かれている．各整数は機械を操作する前における電球の情報を表している．
  左からi ( 1 ≤ i ≤ N ) 番目の整数は西側からi番目の電球の情報を表しており，
  整数が 1 ならば電球の明かりがついていて，0 ならば明かりがついていないことを表す．

出力

標準出力に，作成可能な電球の列に含まれる交互列の長さの最大値を表す整数を1行で出力せよ．

採点基準

採点用データのうち，配点の20%分については，N ≤ 500 を満たす．

採点用データのうち，配点の40%分については，N ≤ 2,000 を満たす．

入出力例

10
1 1 0 0 1 0 1 1 1 0

7

これは問題文中で説明された例である．

10
1 0 0 0 0 1 0 1 0 1

8

西側から4番目の電球のみを操作すると，最大値8を満たす交互列が得られる．

5
1 1 0 1 1

5

西側から数えて2番目から4番目までの電球を操作すると，全ての電球からなる交互列を作ることができる．

3
0 1 0

3

機械を使用しなくても良い場合があることに注意せよ．