AT_joi2020ho_a 長いだけのネクタイ (Just Long Neckties)

[problemUrl]: https://atcoder.jp/contests/joi2020ho/tasks/joi2020ho_a あなたは Just Odd Inventions 社を知っているだろうか？この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ． JOI 社は新商品「長いだけのネクタイ」を開発した．ネクタイは $ N\ +\ 1 $ 種類あり，各種類には $ 1 $ から $ N\ +\ 1 $ までの番号がついている．$ i $ 番目 ($ 1\ \leqq\ i\ \leqq\ N\ +\ 1 $) の種類のネクタイの長さは $ A_i $ である． JOI 社は社員を集め，ネクタイの試着会を行うことにした．試着会には $ N $ 人の社員が参加し，$ j $ 人目 ($ 1\ \leqq\ j\ \leqq\ N $) の社員がはじめに付けているネクタイの長さは $ B_j $ である． 試着会は以下の手順で行われる予定である． 1. まず，試着会で使わないネクタイを $ 1 $ 種類選ぶ． 2. 次に，各社員はそれ以外のネクタイから試着するネクタイを $ 1 $ 種類選ぶ．ただし，どの $ 2 $ 人も同じ種類のネクタイを選ばないようにする． 3. 最後に，各社員は今付けているネクタイを外し，先ほど選んだネクタイを試着する． 長さ $ b $ のネクタイを付けていた社員が，長さ $ a $ のネクタイを試着すると大きさ $ \max\{a\ −\ b,\ 0\} $ の奇妙さを感じる．(ここで，$ \max\{a\ −\ b,\ 0\} $ は，$ a\ -\ b $ と $ 0 $ のうち小さくない方を表す．) 試着会において各社員の感じる奇妙さの最大値を，その試着会の**奇妙さ**とする． 試着会で使わないネクタイが $ k $ 番目の種類のネクタイのとき，試着会の奇妙さとして考えられる最小の値を $ C_k $ とする． 各種類のネクタイの長さ，各社員がはじめに付けているネクタイの長さが与えられた時，$ C_1,\ C_2,\ \ldots,\ C_{N\ +\ 1} $ の値を求めるプログラムを作成せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ N $ $ A_1 $ $ \cdots $ $ A_{N\ +\ 1} $ $ B_1 $ $ \cdots $ $ B_N $

$ C_1,\ C_2,\ \ldots,\ C_{N\ +\ 1} $ の値を，空白区切りで標準出力に $ 1 $ 行で出力せよ． - - - - - -

### 制約 - $ 1\ \leqq\ N\ \leqq\ 200\,000 $. - $ 1\ \leqq\ A_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ +\ 1 $)． - $ 1\ \leqq\ B_j\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ j\ \leqq\ N $)． ### 小課題 1. ($ 1 $ 点) $ N\ \leqq\ 10 $. 2. ($ 8 $ 点) $ N\ \leqq\ 2\,000 $. 3. ($ 91 $ 点) 追加の制約はない. - - - - - - ### Sample Explanation 1 例えば，試着会は次のように行われる． - $ 4 $ 番目の種類のネクタイを使わないことにする． - 社員 $ 1 $ が $ 1 $ 番目の，社員 $ 2 $ が $ 2 $ 番目の，社員 $ 3 $ が $ 3 $ 番目の種類のネクタイを選ぶ． - 各社員が試着する． このとき，各社員が感じる奇妙さは順に $ 2,\ 0,\ 3 $ となるから，この試着会の奇妙さは $ 3 $ である． 社員が選ぶネクタイを変えることで、試着会の奇妙さを $ 1 $ にすることができる．例えば，試着会を次のように行うとする． - $ 4 $ 番目の種類のネクタイを使わないことにする． - 社員 $ 1 $ が $ 2 $ 番目の，社員 $ 2 $ が $ 3 $ 番目の，社員 $ 3 $ が $ 1 $ 番目の種類のネクタイを選ぶ． - 各社員が試着する． このとき，各社員が感じる奇妙さは順に $ 1,\ 1,\ 0 $ となるから，この試着会の奇妙さは $ 1 $ である． これが $ 4 $ 番目の種類のネクタイを使わない場合の試着会の奇妙さの最小値なので，$ C_4\ =\ 1 $ である． - - - - - -