問題

ピ太郎は 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 が連続して登場する回数をそのゲームのスコアとする．

ピ太郎が各ゲームで獲得できるスコアを求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 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 点) 追加の制約はない．

入力例 1

5
1 2 3 4 5
1 2 2 1 3

出力例 1

2
2
1
0
0

例えば {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 を満たしている．

入力例 2

5
1 1 1 1 1
1 1 1 1 1

出力例 2

5
2
1
1
1

カードセット B から得られる数列として考えられるのは {1 1 1 1 1} だけである．

この入出力例は小課題 1,2,3,4 を満たしている．