The first observation is that for each question, the optimal sequence of lineups can be built by starting from the suspect ~p_i~ and adding the suspects one by one from left to right into the current lineup, until at some point this is not possible. When we reach such a suspect that can't be added, we start a new lineup and repeat this process until we reach the suspect ~q_i~.

We can think of this in the following way: for each index ~x~ ~(1 \le x \le n)~, define ~nxt(x)~, which will denote the smallest index greater than ~x~ such that the suspects from ~x~ to ~nxt(x)~ don't form a valid lineup. In other words, if we start building a lineup from ~x~, ~nxt(x)~ is the first suspect we won't be able to add into our set, and he represents the start of a new lineup.

The answer to each query now reduces to finding out how many times must we iterate the function ~nxt~, starting from ~p_i~ until we pass ~q_i~, that is, so that ~nxt(\dots(nxt(p_i))\dots) > q_i~. The solution to this problem has two parts: how do we efficiently calculate ~nxt(x)~ for each index ~x~, and then how to answer the queries efficiently.

~nxt(x)~ can be calculated with the "two pointers" idea. Notice that if ~x < y~, then ~nxt(x) < nxt(y)~ because when moving from index ~x~ to ~x+1~, the lineup we have built thus far remains valid even after we remove ~x~ from the lineup, and possibly it should be extended to the right. To make the insertions and deletions from the current lineup efficient, we have to use a data structure which can support these operations quickly. It is sufficient to use a set container from C++ STL, in which we'll store the left boundaries of the currently inserted height ranges. When inserting a new interval ~[l, r]~, we find the leftmost left boundary that is to the right of ~l~ (using the lower_bound function) and check that it isn't in the interval ~[l, r]~. Analogously, we can find the rightmost left boundary smaller than ~l~ and check that ~l~ isn't contained in that interval. If the mentioned conditions hold, we can add the current suspect to the lineup and add the left boundary to the set.

We can answer the queries using "binary lifting". We'll use ~par[i][j]~ to store ~nxt(\dots(nxt(i))\dots)~, where ~nxt~ is being applied ~2^j~ times. Notice that for all indices ~i~ it holds that ~par[i][0] = nxt(i)~, and also ~par[i][j] = par[par[i][j-1]][j-1]~. Using the mentioned formulas, we can calculate ~par[i][j]~ for all ~i = 1, \dots, n~, and ~j = 0, \dots, \lfloor \log n \rfloor~. We can now answer each query in ~\mathcal O(\log n)~ by descending over ~j~ and at each step moving to the ~2^j~-th ancestor if it does not pass the right boundary (~q~) of the current query.

The total time complexity of the presented algorithm is ~\mathcal O((n+q) \log n)~. The subtasks were meant for competitors who managed to figure out how to calculate ~nxt~ efficiently, or who knew how to answer queries quickly, but who didn't know both.