Longest Increasing Subsequence in Subarray Queries

Given a permutation \(p\) of the integers from \(1\) to \(n\), answer \(q\) queries. Each query provides an interval \([l, r]\) and asks for the length of the longest increasing subsequence (LIS) within the subarray \(p[l..r]\).

An increasing subsequence is a sequence that can be obtained by deleting some (or no) elements without changing the order, where every subsequent element is strictly larger than its predecessor. The length of the LIS is the maximum number of elements in such a subsequence.

inputFormat

The first line contains an integer \(n\) representing the size of the permutation.

The second line contains \(n\) distinct integers \(p_1, p_2, \ldots, p_n\) which form a permutation of \(1\) to \(n\).

The third line contains an integer \(q\) denoting the number of queries.

Each of the following \(q\) lines contains two integers \(l\) and \(r\) (with \(1 \le l \le r \le n\)) representing the bounds of the subarray to be considered.

outputFormat

For each query, output a single line containing one integer representing the length of the longest increasing subsequence in the subarray \(p[l..r]\).

sample

5
1 2 3 4 5
3
1 5
1 3
2 4

5
3
3