Hints: https://atcoder.jp/contests/arc166/editorial/7374

---

In this explanation, we allow \(L_j\) and \(R_j\) to be \(\pm \infty\). There are some slightly inaccurate descriptions around \(\pm \infty\), but they can be easily justified.

Let \(x_0 = -\infty\), \(x_{N+1}=\infty\), \(y_0 = 0\), and \(y_{N+1}=0\).

---

[1] Construction of the optimal solution

Since it is better to take maximal intervals, we can assume the following for every \(j\):

• For every \(j\), there is an \(i\) such that \(L_j = x_i+1\).
• For every \(j\), there is an \(i\) such that \(R_j = x_i-1\).

For each \(i\), let \(a_i\) denote the number of \(j\)’s that satisfy \(L_j = x_i + 1\), and \(b_i\) the number of \(j\)’s that satisfy \(R_j = x_{i+1}-1\). Then, the condition for \(y_i\) can be rewritten as \(a_i - b_i=y_{i+1}-y_i\). Let’s denote the right side \(y_{i+1}-y_i\) as \(c_i\).

Then, we can construct a solution that satisfies the conditions as follows:

• First, determine \(a_i, b_i\) as follows:
  • if \(c_i < 0\), set \(a_i = 0, b_i = |c_i|\).
  • if \(c_i\geq 0\), set \(a_i = |c_i|, b_i = 0\).
• From these \(a_i, b_i\), the multisets \(\{L_j\}\) and \(\{R_j\}\) are determined. Let \((L_1, \ldots, L_M)\) and \((R_1, \ldots, R_M)\) be respectively the elements of \(\{L_j\}\) and \(\{R_j\}\) sorted in ascending order.

In fact, this construction gives one of the optimal solutions (we will outline the proof in [2]). By calculating \(\min\{R_j-L_j\}\) for this solution, you can find the answer to this problem in \(O(N)\) time (\(M\) can be huge, so you need to implement it properly, but it’s simple).

---

[2] Proof of the optimality (outline)

First, the following holds:

You are given \(L_1\leq \cdots \leq L_M\) and \(R_1\leq \cdots \leq R_M\). If \(R\) can be freely rearranged, \(\min\{R_j-L_j\}\) is maximized when \(R\) is in ascending order.

This can be proved by the fact that, for an \(R\) that is not in ascending order, \(\min\{R_j-L_j\}\) does not decrease by adjacent swaps that reduce the inversion number of \(R\).

---

In particular, when \(\{a_i\}, \{b_i\}\) are determined (the multisets \(\{L_j\}\), \(\{R_j\}\) are determined), it is optimal to arrange them in ascending order and correspond them. From now on, we will treat \(\min\{R_j-L_j\}\) as something determined from \(\{a_i\},\{b_i\}\) under this construction.

All that remains is to show that it is optimal to determine \(\{a_i\},\{b_i\}\) as in [1]. Since \(a_i-b_i\) is a constant, the only freedom in determining \(\{a_i\},\{b_i\}\) is to repeat the operation of selecting one \(i\) and incrementing \(a_i,b_i\) from the method determined in [1].

Therefore, it is sufficient to confirm that \(\min\{R_j-L_j\}\) does not increase by the operation of selecting one \(i\) and incrementing \(a_i,b_i\). In this operation, the sorted sequences of elements of \(\{L_j\}\) and \(\{R_j\}\) change as follows:

• \((\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)\).

Here, the number of \(j\) such that \(L_j\leq x_{i}+1\) is \(t\), and the number of \(j\) such that \(R_j\leq x_{i+1}-1\) is \(s-1\).

If \(s\leq t\), it can be easily confirmed that \(R_j-L_j\) in the new sequence is less than or equal to one of the differences in the original sequence. If \(i\neq N\), then from \(0<y_{i+1}\) we have \(t-(s-1)>0\), so \(s\leq t\) does hold and we are done. If \(i=N\), only the term \(\infty\) is added as \(R_j-L_j\), so \(\min\{R_j-L_j\}\) does not increase.

This completes the proof of the optimality of the solution in [1].