\(d = \max_j(R_j - L_j + 1)\) とします．つまり，入力区間の要素数の最大値です．

条件を満たす \(A\) について \(\max(A_1, A_2, \ldots, A_N)\) としてありうる最小値を \(\mathrm{ANS}\) と書くことにします．

[1] \(\mathrm{ANS}\) は \(d\) 以上であること

\(d = R_j - L_j + 1\) であるような \(j\) をとります．

\(d\) 個の整数 \(A_{L_j}, A_{L_j+1}, \ldots, A_{R_j}\) がすべて相異なることが必要です．さらに \(A_i\) が正整数であることから，\(A\) は相異なる正整数 \(d\) 個を含む必要があります．したがって条件を満たすどのような \(A\) についても

\[\max(A_1,A_2,\ldots,A_N)\geq d\]

が成り立ちます．このことから，\(\mathrm{ANS}\geq d\) が分かります．

[2] \(\mathrm{ANS}\) は \(d\) 以下であること

正整数列 \(A\) を

\[ A_i = ((i-1)\bmod d) + 1\qquad (1\leq i\leq N) \]

によって定めます．連続する \(d\) 個以下の整数 \(i\) について，\(i\bmod d\) は相異なるため，この正整数列は問題の条件をすべて満たします．

任意の \(i\) について \(A_i\leq (d-1)+1=d\) なので，この \(A\) は

\[\max(A_1,A_2,\ldots,A_N) \leq d\]

を満たしています．したがって \(\mathrm{ANS}\leq d\) が成り立ちます．

[3] まとめ

以上により \(\mathrm{ANS}=d\) であることが示されました．また，対応する正整数列 \(A\) の例は [2] で解説されています．

• 解答例：https://atcoder.jp/contests/arc222/submissions/76530117

[1] のように未知の量 \(\mathrm{ANS}\) について，いくつ以上であるという情報を得ることを \(\mathrm{ANS}\) を下から評価するといいます．同様に [2] は \(\mathrm{ANS}\) を上から評価しているといえます．

最適化問題（ある量としてありうる最大値や最小値を求める問題）では，答を上から評価する，または下から評価するというのは基本的な考え方です．サンプルやランダムケースを観察しながら一方向の評価の方法を考えていくと，それが解法につながるということは珍しくありません．