Illumination

Time Limit : 1 sec, Memory Limit : 262144 KB

電飾(Illumination)

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 ≤ iN ) 番目の整数は西側から i 番目の電球の情報を表しており,整数が 1 ならば電球の明かりがついていて,0 ならば明かりがついていないことを表す.

出力

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

入出力例

入力例 1

10
1 1 0 0 1 0 1 1 1 0

出力例 1

7

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


入力例 2

10
1 0 0 0 0 1 0 1 0 1

出力例 2

8

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


入力例 3

5
1 1 0 1 1

出力例 3

5

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


入力例 4

3
0 1 0

出力例 4

3

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

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 12th Japanese Olympiad in Informatics , 2013-2-10
http://www.ioi-jp.org/