This problem is the well-known range query LIS problem.

The problem can be solved in $O(n \log^2 n + q \log n)$ time. A tutorial post by gs14004 can be found at Codeforces: 1 and 2. The paper Semi-local string comparison: algorithmic techniques and applications is also useful to understand the algorithm.

A simpler (and more competitive-programmable) solution is running in $O(n \sqrt n \log n + q \log n)$ time, which is left as an exercise to the reader.