Let \(d = \max_j(R_j - L_j + 1)\), that is, the maximum number of elements among the input intervals.

Let \(\mathrm{ANS}\) denote the minimum possible value of \(\max(A_1, A_2, \ldots, A_N)\) for a sequence \(A\) satisfying the condition.

[1] \(\mathrm{ANS}\) is at least \(d\)

Take \(j\) such that \(d = R_j - L_j + 1\).

It is required that the \(d\) integers \(A_{L_j}, A_{L_j+1}, \ldots, A_{R_j}\) are all distinct. Since each \(A_i\) is a positive integer, \(A\) must contain \(d\) distinct positive integers. Therefore, for any \(A\) satisfying the condition,

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

holds. From this, we have \(\mathrm{ANS}\geq d\).

[2] \(\mathrm{ANS}\) is at most \(d\)

Define the positive integer sequence \(A\) by

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

Since \(i\bmod d\) takes distinct values for any \(d\) or fewer consecutive integers \(i\), this positive integer sequence satisfies all the conditions of the problem.

For any \(i\), we have \(A_i\leq (d-1)+1=d\), so this \(A\) satisfies

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

Therefore, \(\mathrm{ANS}\leq d\) holds.

[3] Summary

We have now shown that \(\mathrm{ANS}=d\). Also, an example of the corresponding positive integer sequence \(A\) is described in [2].

• Sample solution: https://atcoder.jp/contests/arc222/submissions/76530117

As in [1], obtaining information that an unknown quantity \(\mathrm{ANS}\) is at least some value is called bounding \(\mathrm{ANS}\) from below. Similarly, [2] can be said to be bounding \(\mathrm{ANS}\) from above.

In optimization problems (problems asking for the maximum or minimum possible value of some quantity), bounding the answer from above or from below is a fundamental approach. It is not uncommon that, while observing samples and random cases, thinking about one direction of bounding leads to a solution.