As this is a permutation, every number from 1 to n exists exactly once. If the interval of the query corresponds to a larger answer, say the answer is K, then all 1,2,... ,K-1 must all be in the interval, which means that the longer the interval is.
So, we can set pos_i to denote the position where the number i appears and then set the interval [l_k,r_k] to denote the smallest interval that corresponds to when the answer is k + 1. [l_k,r_k] can be obtained from [l_{k-1},r_{k-1}] with pos_{k}.
Once the above intervals have been preprocessed, for each query, the binary search method can be used to find the answer.
Time Complexity: O(n + q \log n)