First, let’s consider the case with one query.

Suppose the input is \(B=(B_1,\cdots,B_N)\). First, let \(B_m=\max(B)\). When decomposing \(B\) into \(XYZ\), we will consider the cases based on where \(B_m\) is included among \(X, Y, Z\).

First, the case where \(B_m\) is included in \(Y\) is simple. Since \(\max(Y)\) is determined to be \(B_m\), there is no harm in making \(Y\) larger. Therefore, we only need to consider the pattern \(X=(B_1), Y=(B_2,\cdots,B_{N-1}), Z=(B_N)\).

Next, let’s consider the case where \(B_m\) is included in \(X\). By the same reasoning as before, \(Y\) can be assumed to contain only one element. By trying all possible positions for \(Y\), we can calculate the answer.

The case where \(B_m\) is included in \(Z\) is similar to the case for \(X\). By reversing the sequence, we can solve it with exactly the same code.

Next, let’s consider answering multiple queries.

The case where \(B_m\) is included in \(Y\) is still simple and can be handled with a simple RMQ.

There are two main approaches to handle the case where \(B_m\) is included in \(X\).

The first approach is to manage \(\max(Z)\) for each \(Y\). We will process the queries in ascending order of \(R_i\). As \(R_i\) increases, \(\max(Z)\) for each \(Y\) will also increase. This increase can be represented by range addition, so we can solve it using a segment tree with range addition and range minimum query.

The second approach is to manage \(Y\) for each \(\max(Z)\). Similar to the first approach, we process the queries in ascending order of \(R_i\). We manage the possible values of \(\max(Z)\) with a stack and also manage the possible minimum values for \(Y\). This can be implemented with a simple segment tree for range minimum query.

Using either approach, the time complexity will be \(O((N+Q) \log N)\).

Sample Solution for Approach 1 (C++)

Sample Solution for Approach 2 (C++)