ヒント → https://atcoder.jp/contests/arc166/editorial/7181

---

本解説において，\(L_j\) や \(R_j\) が \(\pm \infty\) であることも許容するものとします．また \(\pm \infty\) の周りで少し不正確な記述をしている場所がありますが，正当化は容易です．

\(x_0 = -\infty\), \(x_{N+1}=\infty\), \(y_0 = 0\), \(y_{N+1}=0\) とします．

---

[1] 最適解の構築

区間は極大にとった方がよいので，任意の \(j\) に対して次が成り立つとしてよいです：

• 任意の \(j\) に対して \(L_j = x_i+1\) となる \(i\) が存在する．
• 任意の \(j\) に対して \(R_j = x_i-1\) となる \(i\) が存在する．

各 \(i\) に対して，\(L_j = x_i + 1\) となる \(j\) の個数を \(a_i\), \(R_j = x_{i+1}-1\) となる \(i\) の個数を \(b_i\) と書くことにします．すると，\(y_i\) に関する条件は，\(a_i - b_i=y_{i+1}-y_i\) という条件に言い換えることができます．この右辺 \(y_{i+1}-y_i\) を \(c_i\) と書きます．

すると，まず次のようにして条件を満たす解がひとつ構成できます：

• まず次のように \(a_i, b_i\) を定める：
  • \(c_i < 0\) ならば，\(a_i = 0, b_i = |c_i|\) とする．
  • \(c_i\geq 0\) ならば，\(a_i = |c_i|, b_i = 0\) とする．
• このように定めた \(a_i, b_i\) から，多重集合 \(\{L_j\}\), \(\{R_j\}\) が定まる．これらの多重集合の要素を昇順に並べたものをそれぞれ \((L_1, \ldots, L_M)\), \((R_1, \ldots, R_M)\) とする．

実はこの構成は最適解のひとつを与えます（[2] で証明を述べます）．この解に対する \(\min\{R_j-L_j\}\) を計算することで，本問題の答を \(O(N)\) 時間で求めることができます （\(M\) は巨大になりうるため，適切な実装を行う必要がありますが，簡単です）．

---

[2] 最適性の証明（概略）

まず次が成り立ちます：

\(L_1\leq \cdots \leq L_M\) かつ \(R_1\leq \cdots \leq R_M\) が与えられる．\(R\) を自由に並べ替えられるとき，\(\min\{R_j-L_j\}\) が最大であるのは \(R\) が昇順に並んでいるときである．

これは，\(R\) が昇順でないような列に対して，\(R\) の転倒数を減らすような隣接互換によって \(\min\{R_j-L_j\}\) が減少しないことから証明できます．

---

特に \(\{a_i\}, \{b_i\}\) が定まっている（多重集合 \(\{L_j\}\), \(\{R_j\}\)が定まっている）ときに，それぞれを昇順に並べて対応させることが最適であることが分かりました．以下このような構成を前提とし，\(\min\{R_j-L_j\}\) は \(\{a_i\},\{b_i\}\) から定まるものとして扱います．

あとは [1] のように \(\{a_i\},\{b_i\}\) を定めるのが最適であることを示せばよいです．\(a_i-b_i\) が定数であるため，\(\{a_i\},\{b_i\}\) の定め方には [1] で定めた方法から「\(i\) をひとつ選び \(a_i,b_i\) をインクリメントする」という操作を繰り返すという自由度しかありません．

よって，「\(i\) をひとつ選び \(a_i,b_i\) をインクリメントする」という操作によって \(\min\{R_j-L_j\}\) が非増加であることを確かめればよいです．この操作では \(\{L_j\}\), \(\{R_j\}\) のソート列は次のように変化します．

• \((\ldots, \ L_s, L_{s+1}, \ldots, L_t, \ldots) \to (\ldots, L_s, L_{s+1}, \ldots, L_t, x_{i}+1, \ \ldots)\).
• \((\ldots, \ R_s, R_{s+1}, \ldots, R_t, \ldots) \to (\ldots, \ x_{i+1}-1,R_s, R_{s+1}, \ldots, R_t,\ \ldots)\).

ここで，\(L_j\leq x_{i}+1\) となる \(j\) の個数を \(t\)，\(R_j\leq x_{i+1}-1\) となる \(j\) の個数を \(s-1\) としています．

ここで \(s\leq t\) ならば，新たな列における \(R_j-L_j\) は元の列におけるどれかの差分以下であることが簡単に確かめられます．\(i\neq N\) ならば \(0<y_{i+1}\) より \(t-(s-1)>0\) なので，\(s\leq t\) は成り立っているのでよいです．\(i=N\) のときは \(R_j-L_j\) として新たに \(\infty\) という項が加わるだけなので， \(\min\{R_j-L_j\}\) は非増加です．

以上で [1] の解の最適性が示されました．