There are various solutions to this problem, but here we introduce admin’s solution, which can be explained concisely.

First, for \(1\leq k\leq N\) and an integer \(x\), we define \(f_k(x)\) as follows:

\[ f_k(x) = \Big(\text{ The minimum value of } \sum_{i=k}^{N-1}|A_{i+1}-A_i| \text{ under the constraints } A_k = x, L_i \leq A_i \leq R_i\ (k + 1 \leq i \leq N) \Big) \]

From the definition, it is clear that \(f_N(x) = 0\). Also, we define the set of integers \(I_k\) as follows:

\[ \begin{aligned} I_k & \coloneqq \underset{x\in [L_k, R_k] \cap \mathbb{Z}}{\mathrm{argmin }} f_k(x) \\ & = \Big\lbrace x \in [L_k, R_k] \cap \mathbb{Z} \Bigm\vert f_k(x) = \min_{x'\in [L_k, R_k] \cap \mathbb{Z}} f_k(x') \Big\rbrace. \end{aligned} \]

Then, the following proposition holds.

Proposition 1.

1. \(I_k\) can be represented as an interval of integers for \(1\leq k \leq N\). That is, there exist integers \(l_k, r_k \ (l_k \leq r_k)\) such that \(I_k = [l_k, r_k] \cap \mathbb{Z}\). Hereafter, we use these \(l_k, r_k\).
2. \(I_N = [L_N, R_N]\), and for \(k < N\),
   • \(I_k = [L_k, R_k] \cap I_{k+1}\) if \([L_k, R_k] \cap I_{k+1} \neq \emptyset\).
   • \(I_k = \lbrace R_k \rbrace\) if \(R_k < l_{k+1}\).
   • \(I_k = \lbrace L_k \rbrace\) if \(L_k > r_{k+1}\).
3. Let \(m_k =\displaystyle \min_{x \in [L_k, R_k] \cap \mathbb{Z}} f_k(x)\). For \(1 \leq k < N\),

   \[ f_k(x) = \begin{cases} m_{k+1} + l_k - x & (x < l_k)\\ m_{k+1} & (x\in [l_k, r_k])\\ m_{k+1} + x - r_k & (r_k < x) \end{cases} \]

This proposition can be proved by using induction in descending order of \(k\). From Proposition 1, there exist integers \(l_k, r_k\) such that \(I_k = [l_k, r_k]\). Also, following Proposition 1.2, we can determine each \(l_k, r_k\) in descending order of \(k\).

Next, we consider constructing the lexicographically smallest solution. From the definition of \(I_1\), it is fine to set \(A_1 = \min I_1 = l_1\). Hereafter, for \(k \geq 2\), we consider determining \(A_k\) when \(A_1, \dots, A_{k-1}\) have been determined. Here, among \(x\in [L_k, R_k]\) that minimizes \(|x - A_{k-1}| + f_k(x)\), the smallest one should be chosen as \(A_k\). By using Proposition 1.3 for calculation, it can be seen that \(A_k = \max\lbrace \min \lbrace A_{k-1}, r_k \rbrace , L_k \rbrace\). Therefore, we can determine each \(A_k\) in ascending order of \(k\).

Sample Implementation (C++):

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;

	vector<ll> L(n), R(n);
	for(int i = 0; i < n; i++) cin >> L[i] >> R[i];

	vector<ll> l(n), r(n);
	l.back() = L.back(), r.back() = R.back();

	for(int i = n - 2; i >= 0; i--) {
		if(R[i] < l[i + 1]) {
			l[i] = r[i] = R[i];
		} else if(L[i] > r[i + 1]) {
			l[i] = r[i] = L[i];
		} else {
			l[i] = max(L[i], l[i + 1]);
			r[i] = min(R[i], r[i + 1]);
		}
	}

	vector<ll> a(n);
	a.front() = l.front();

	for(int i = 1; i < n; i++) { a[i] = clamp(a[i - 1], L[i], r[i]); }
	for(int i = 0; i < n; i++) { cout << a[i] << (i == n - 1 ? '\n' : ' '); }
}