A chain is defined as the sequence of integers $$$1 \rightarrow 2 \rightarrow 3 \rightarrow \dots \rightarrow k$$$.

Given 2 arrays $$$A$$$ and $$$B$$$

• Does the array has a subsequence whose values form a chain. If so, what is the maximum length of such a chain.
• Notice that the maximal chain is not unique. Define min-lex maximal chain subsequence as the subsequence which is lexicographically smaller than any other maximal chain subsequence.
• Find the the min-lex maximal chain of A and B
• Are the indices of min-lex maximal chain of $$$A[L \dots R]$$$ and $$$B[L \dots R]$$$ same?
• How many subarrays such that min-lex maximal chain of A and B are same?
• Find the length of maximal chain of $$$A[L \dots R]$$$

I created a video on the ideas used in this problem