• N <= 2 の場合を処理しておく
◦ A = [1] のとき答えは1
◦ A = [1,1], [2,2] のとき答えは0
◦ A = [1,2], [2,1] のとき答えは2
• 上記以外の場合は必ず答えが0か1となる
◦ 両端が一致している場合、答えは0
◦ 両端が異なる場合、先頭を1と仮定すると [ 1, ?, ?,..., ?, 2] のようになっていて、A_i = 1 かつ A_{i+1} = 2 となる箇所は必ず存在する
▪ [?, ?,..., ?] のどこかに [1,2] が存在するなら [ 1,?,...,?,1,2,?,...,?,2] のように操作できて答えは0
▪ それ以外は [1,?,?,...,?,1,2] か [1,2,?,?,...,?,2] のどちらかの操作ができ答えは1
12