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++)