Consider the set of all segments of length \(2^i\), where \(i\) is an integer such that \(0 \leq i \leq \lfloor\log_2 N\rfloor\). You can thus answer every query by first finding \(k = \lfloor\log_2 (R-L+1)\rfloor\), then responding with the two segments that correspond to \([L, L+2^k-1]\) and \([R-2^k+1, R]\).

We can prove that the number of segments is low enough pretty easily: it’s approximately \(N \cdot (\lfloor\log_2 N\rfloor + 1) \leq 4000 \cdot 12 = 48000\). In fact, the upper bound is somewhat less than that, as there are \(N+1-2^k\) segments of length \(2^k\).

This technique is used in a data structure called the sparse table, which allows quickly computing range minimums, maximums, and/or GCDs (more generally, any computable semilattice) by combining the results of two ranges that are allowed to overlap.