AT_arc175_c [ARC175C] Jumping Through Intervals

给定 $N$ 个整数对 $(L_1, R_1), (L_2, R_2), \dots, (L_N, R_N)$。其中，对于所有 $1 \leq i \leq N$，都有 $L_i \leq R_i$。 我们称满足以下条件的 $N$ 元整数列 $A = (A_1, A_2, \ldots, A_N)$ 为**良好整数列**： - 对于所有 $1 \leq i \leq N$，都有 $L_i \leq A_i \leq R_i$。 请在所有使得 $\displaystyle \sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的**良好整数列** $A$ 中，输出字典序最小的一个。 数列的字典序定义如下：设数列 $S = (S_1, S_2, \ldots, S_{|S|})$，$T = (T_1, T_2, \ldots, T_{|T|})$。$S$ 的字典序小于 $T$，当且仅当下列两条之一成立： 1. $|S| < |T|$ 且 $(S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|})$。 2. 存在整数 $1 \leq i \leq \min\{|S|, |T|\}$，使得 - $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$， - 且 $S_i < T_i$。

输入按以下格式从标准输入读入： > $N$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_N$ $R_N$

请将答案以 $1$ 行输出： > $A_1$ $A_2$ $\ldots$ $A_N$

### 数据范围 - 输入的所有数均为整数。 - $2 \leq N \leq 5 \times 10^5$ - $0 \leq L_i \leq R_i \leq 10^9$ ### 样例解释 1 $(A_1, A_2, A_3, A_4) = (8, 8, 4, 5)$ 是一个良好整数列。此时 $\sum_{i=1}^{N-1} |A_{i+1} - A_i| = |8 - 8| + |4 - 8| + |5 - 4| = 5$，这是 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 的最小值。 ### 样例解释 2 当使 $\sum_{i=1}^{N-1} |A_{i+1} - A_i|$ 最小的良好整数列 $A$ 有多个时，请输出其中字典序最小的一个。 由 ChatGPT 4.1 翻译