Given an array A of length N, what is the best approach to answer queries of the form (i,j) where i and j are the indices of the array. Answer to a query (i,j) is the length of longest increasing subsequence of subarray from i to j. I am thinking of making a 2-D matrix which stores the length of LIS of all subarrays and then answering queries in O(1). How should I go about making that 2-D matrix? Or is there a better approach?