電飾 (Illumination)

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

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

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

例

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

○ ○ ● ● ○ ● ○ ○ ○ ●

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

○ ○ ● ○ ● ○ ● ○ ○ ●

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

○ ○ ● ○ ● ○ ● ○ ○ ●

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

○ ○ ● ● ○ ● ○ ● ○ ●

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

○ ○ ● ● ○ ● ○ ● ○ ●

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

課題

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

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

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

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

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

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

JOI 2013 · JCIOI · CC BY-SA 4.0