Company: Google_IITR
Difficulty: medium
Tricky subarrays Problem Description You are given a permutation A of length N . There are Q queries. In each query, you are given L and R . Determine the number of subsequences B from the subarray A[L:R] such that |B| = max(B) . |B| is the length of the array B . Notes 1-based indexing is used in this question. A permutation P of size N is an array where each number from 1 to N appears exactly once. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. An array B is called a subarray of A if it forms a contiguous subsequence of A , i.e., if it is equal to A L , A L+1 , ..., A R-1 , A R for some L, R . Examples Example 1: Assumptions: N = 3 A = [2,1,3] Q = 1 Queries = [[2,3]] Approach: The subarray from L=2 to R=3 is [1, 3] . There is only one subsequence [1] that satisfies the given condition ( |B|=1 , max(B)=1 ). The subsequence [3] does not satisfy the condition ( |B|=1 , max(B)