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

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

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

例

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

○ ○ ● ● ○ ● ○ ○ ○ ●

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

○ ○ ● ○ ● ○ ● ○ ○ ●

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

○ ○ ● ○ ● ○ ● ○ ○ ●

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

○ ○ ● ● ○ ● ○ ● ○ ●

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

○ ○ ● ● ○ ● ○ ● ○ ●

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

課題

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

制限

採点基準

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

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

入力例 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

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

IOI 国ではこのたび新たに鉄道を敷設した．IOI 国の鉄道を走る列車はいくつかの車両が連結されたものであり，車両には I，O の 2 種類がある．車両はそれぞれ異なる種類の車両としか連結できない．また，列車に運転席を設ける関係上，列車の両端の車両は種類 I でなければならない．列車は車両の種類を表す文字を順につなげた文字列で表され，列車の長さはその文字列の長さであるとする．たとえば， IOIOI の順に車両を連結すると長さ 5 の列車を編成でき，また車両 I は単独で長さ 1 の列車である．車両を OIOI や IOOI といった順に並べても列車を編成することはできない．

いくつかの車両が 2 つの車庫に格納されている．それぞれの車庫の中には車両が一列に並んでいる．列車を編成するときは車庫から車両を出してきて車庫前で連結していく．車庫から出せる車両は最も車庫の入り口に近い車両のみであるが，どちらの車庫から車両を出すかの順番については自由である．

列車を編成する前に，車両を好きなだけ車庫から出して別の待機用レールに移すことができる．一度待機用レールに移した車両は今後列車を編成するために使うことはできない．また，一度列車の編成を始めるとその編成が終わるまでの間は車両を車庫から待機用レールに移すことはできない．

列車を編成するとき，車庫内の全ての車両を使い切る必要はない．すなわち，列車の編成を終えた後，車庫内に使われなかった車両が残っていても構わない．

IOI 国では鉄道に乗る人がとてもたくさんいると考えられているので，できるだけ長い列車を編成したい．

列車を編成している途中であり，このとき車庫にある車両を待機用レールに移すことはできない．この図は入出力例 1 に対応している．

課題

車庫に格納された車両の情報が与えられたとき，編成できる列車の長さの最大値を求めるプログラムを作成せよ．それぞれの車庫に格納された車両の列は 2 種類の文字 I，O のみからなる文字列で表され，2 つの車庫の情報はそれぞれ長さ M の文字列 S および長さ N の文字列 T として与えられる．各文字が 1 つの車両を表し，その文字は車両の種類と同じである．文字列の 1 文字目は最も車庫の入り口に近い車両を表し，末尾の文字が車庫の最も奥にある車両を表す．

制限

採点基準

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

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

入力例 1

5 5
OIOOI
OOIOI

出力例 1

7

S によって表される車庫を車庫 S とし，T によって表される車庫を車庫 T としよう．このとき，たとえば車庫 S から最初の 1 車両，車庫 T から最初の 2 車両を出して待機させた後，車庫 S，車庫 S，車庫 T，車庫 S，車庫 S，車庫 T，車庫 T の順番に車両を出せば，長さ 7 の列車 IOIOIOI を編成できる．

他にも，車庫 S から最初の 1 車両，車庫 T から最初の 2 車両を出して待機させた後，車庫 T，車庫 T，車庫 S，車庫 S，車庫 T，車庫 S，車庫 S の順番に車両を出すことでも長さ 7 の列車を編成できる．これより長い列車を編成することはできないので 7 を出力する．

入力例 2

5 9
IIIII
IIIIIIIII

出力例 2

1

1 つの車両のみからなる列車 I も列車としての条件を満たすことに注意せよ．

あなたは，ある大きな屋敷に迷い込んでしまった．この屋敷は正方形の部屋が東西南北に格子状に，東西方向に M 列，南北方向に N 行の合計 M \times N 個並んだ構造をしている．西から x 列目 (1 \leqq x \leqq M)，南から y 行目 (1 \leqq y \leqq N) にある部屋を (x, y) で表す．

東西南北に隣り合う 2 部屋の間は，壁の中央にある扉により結ばれている．それぞれの扉は，閉じていて通行不可能な状態か，開いていて通行可能な状態のいずれかにある．扉が開いているとき，それらの部屋の中央間を移動するのに 1 分間かかる．また，いくつかの部屋の中央にはスイッチがあり，スイッチを 1 分間押し続けると，屋敷内のすべての扉の開閉の状態が切り替わる．

今，東西に隣り合う 2 部屋を結ぶすべての扉は閉じていて，南北に隣り合う 2 部屋を結ぶすべての扉は開いている．あなたは今部屋 (1, 1) の中央にいて，部屋 (M, N) の中央まで最短時間で移動したい．

課題

屋敷の大きさ M, N および，スイッチのある K 個の部屋の位置 (X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K) が与えられる．東西に隣り合う 2 部屋を結ぶすべての扉は閉じていて，南北に隣り合う 2 部屋を結ぶすべての扉は開いている状態から始めて，部屋 (1, 1) の中央から部屋 (M, N) の中央まで移動するのに最短で何分かかるかを求めるプログラムを作成せよ．ただし，部屋 (M, N) に辿り着くことができないときはそれを指摘せよ．

制限

採点基準

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

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

採点用データのうち，配点の 50 %分については，これら 2 つの条件の少なくとも一方を満たす．また，これら 2 つの条件の両方を満たすような採点用データはない．

入力例 1

3 2 1
1 2

出力例 1

4

この例では，以下の行動によって 4 分間で部屋 (1, 1) の中央から部屋 (3, 2) の中央へ移動することができ，これが最短である．

• 部屋 (1, 2) の中央へ移動する．
• 部屋 (1, 2) の中央のスイッチを押す．
• 部屋 (2, 2) の中央へ移動する．
• 部屋 (3, 2) の中央へ移動する．

このときの屋敷の様子が以下の図に表されている．図では右方向が東，上方向が北であり，×印はあなたの位置，○印はスイッチを表す．

入力例 2

3 2 1
2 1

出力例 2

-1

この例では，あなたは部屋 (3, 2) に辿り着くことができない．

入力例 3

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

出力例 3

25

この例では，最初の屋敷の様子は以下の図のようになっている．部屋 (1, 1) や部屋 (M, N) の中央にスイッチがある可能性もあることに注意せよ．

JOIOI の塔とは，1 人で遊ぶ円盤を使ったゲームである．

このゲームは，J，O，I のいずれかの文字が書かれたいくつかの円盤を用いて行う．円盤は直径が互いに異なり，ゲーム開始時にはこれらの円盤は直径の大きいものから順に下から上に向かって積まれている．あなたは，これらの円盤を用いて，出来るだけ多くのミニ JOIOI の塔を作りたい．ミニ JOIOI の塔とは 3 枚の円盤からなり，円盤の直径が小さいものから順に読んで JOI もしくは IOI と読めるものである．ただし，同じ円盤を 2 度以上使うことはできない．

`JOIOII` からはミニ JOIOI の塔が 2 つ作れる

課題

用意された円盤に書かれた文字がそれぞれ円盤の直径が小さいものから順に長さ N の文字列 S として与えられる．これらの円盤を使って作ることのできるミニ JOIOI の塔の個数の最大値を求めるプログラムを作成せよ．

制限

採点基準

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

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

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

入力例 1

6
JOIIOI

出力例 1

2

JOIIOI は JOI および IOI をそれぞれ 1 つずつ部分列として含んでおり，作ることのできるミニ JOIOI の塔は 2 つである．

入力例 2

5
JOIOI

出力例 2

1

部分列として JOI および IOI を含んでいるが，文字を 2 度以上使うことはできないため同時に取り出すことはできない．

入力例 3

6
JOIOII

出力例 3

2

この入出力例は問題文中の例に対応している．

入力例 4

15
JJOIIOOJOJIOIIO

出力例 4

4

バブルソートとは，列をソートするアルゴリズムの 1 つである．長さ N の数列 A を昇順にソートしたいとしよう．バブルソートは，隣り合う 2 つの数で大小関係が崩れているものがあれば，それらの位置を交換する．これを，数列を前から順に走査しながら行う．すなわち，A_i > A_{i + 1} となっている場所があれば，その 2 数を交換するということを，i = 1, 2, \ldots, N - 1 に対してこの順で行うのが 1 回の走査である．この走査を N − 1 回繰り返すことで，数列を昇順にソートできることが知られている．

数列 A のバブルソートによる交換回数とは，数列 A に上記のアルゴリズムを適用した時に，整数の交換が行われる回数である．（バブルソートとして知られるアルゴリズム及び実装には，ループの順番や範囲，及び終了条件など，細かな差異がある場合がある．ただし，同じ数列に適用した際の整数の交換回数はそれらの差異により変化しないことが知られている．）

例えば，以下のプログラムは長さ n の整数の配列 a をバブルソートによりソートする関数を C 言語で記述したものである．

void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* 以下 3 行が 1 回の整数の交換に相当 */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

課題

長さ N の数列 A が与えられる．数列 A の任意の場所の 2 つの整数を 1 回だけ交換した数列 A' を作るとする．数列 A' のバブルソートによる交換回数の最小値を求めるプログラムを作成せよ．（最初に交換する 2 つの整数は必ずしも隣り合っている必要はないことに注意せよ．）

制限

（注）過去問移植時に制約を修正．

採点基準

採点用データのうち，配点の 10 %分については，N \leqq 1 000 を満たし，任意の i, j (1 \leqq i < j \leqq N) について A_i \neq A_j を満たす．

採点用データのうち，配点の 30 %分については，N \leqq 5\,000 を満たし，任意の i, j (1 \leqq i < j \leqq N) について A_i \neq A_j を満たす．

採点用データのうち，配点の 80 %分については，任意の i, j (1 \leqq i < j \leqq N) について A_i \neq A_j を満たす．

入力例 1

5
10
3
6
8
1

出力例 1

0

数列 A の最初の 10 と最後の 1 を交換することにすると，数列 A' はソート済みの列となり，バブルソートの交換回数は 0 となる．

入力例 2

5
3
1
7
9
5

出力例 2

2

数列 A の 3 番目の 7 と最後の 5 を交換することで，数列 A' は 3, 1, 5, 9, 7 となる．A' のバブルソートによる交換回数は 2 である．

入力例 3

3
1
2
3

出力例 3

1

最初から数列 A がソートされている場合でも，数列 A' を作る際に交換を行わなければならない．