AT_otemae2019_c カード並べ 2 (Arranging Card 2)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_c ピ太郎は $ N $ 枚のカードセットを $ 2 $ 組持っている．$ 1 $ 組目のカードセットには $ A $ と名前がついていて，先頭から順に $ a_1 $ から $ a_N $ の数が書かれている．$ 2 $ 組目のカードセットには $ B $ と名前がついていて，先頭から順に $ b_1 $ から $ b_N $ の数が書かれている． ピ太郎はカードセット $ B $ を好きなように，いつでも何回でも並べ替えられる． ピ太郎は次のようなゲームを $ N $ 回行う． - $ i $ $ (1\ \leq\ i\ \leq\ N) $ 回目のゲームでは．カードセット $ A $ の先頭 $ i $ 枚に書かれた数を順に並べた数列を $ C_i $ とする． - カードセット $ B $ の各カードに書かれた数を順に並べた数列の中に数列 $ C_i $ が連続して登場する回数を最大化するようにカードセット $ B $ を並び替える． - ただし，$ C_i $ 同士の登場位置は重なってはいけない．例えば数列 `{1 2 1 2 1 2 1 2}` は `{(1 2 1 2) (1 2 1 2)}` と考えると，数列 `{1 2 1 2}` が $ 2 $ 回登場している．このとき，`{(1 2 1 2) 1 2 1 2}` ，`{1 2 (1 2 1 2) 1 2}` ，`{1 2 1 2 (1 2 1 2)}` の $ 3 $ 回と数えることは出来ない． - カードセット $ B $ の各カードに書かれた数を順に並べた数列の中に数列 $ C_i $ が連続して登場する回数をそのゲームのスコアとする． ピ太郎が各ゲームで獲得できるスコアを求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ a_1 $ $ a_2 $ $ \cdots $ $ a_N $ $ b_1 $ $ b_2 $ $ \cdots $ $ b_N $

標準出力に$ N $ 行で出力せよ．$ i $ ($ 1\ \leq\ i\ \leq\ N $) 行目には，$ i $ 回目のゲームでピ太郎が獲得できるスコアを出力せよ．

### 制約 - 入力はすべて整数である． - $ 2\ \leq\ N\ \leq\ 100\,000 $． - $ 1\ \leq\ a_i,\ b_i\ \leq\ 100\,000 $ $ (1\ \leq\ i\ \leq\ N) $． ### 小課題 1. ($ 16 $ 点) $ N\ \leq\ 8 $． 2. ($ 10 $ 点) $ a_i\ =\ 1 $ $ (1\ \leq\ i\ \leq\ N) $． 3. ($ 24 $ 点) $ N\ \leq\ 1\,000 $． 4. ($ 50 $ 点) 追加の制約はない． ### Sample Explanation 1 例えば `{1 2 3 2 1}` と並べ替えることで $ C_1 $ を $ 2 $ 個，`{3 1 2 1 2}` と並べ替えることで $ C_2 $ を $ 2 $ 個，`{2 1 2 3 1}` と並べ替えることで $ C_3 $ を $ 1 $ 個登場させることができる． この入出力例は小課題 $ 1,3,4 $ を満たしている． ### Sample Explanation 2 カードセット $ B $ から得られる数列として考えられるのは `{1 1 1 1 1}` だけである． この入出力例は小課題 $ 1,2,3,4 $ を満たしている．