Given an array, compute the prefix maxima array and remove all the duplicates. How many subsequences of the original array can you create such that the prefix maxima of the subsequence is equal to the prefix maxima of the original array (after removing the duplicates from both)?

I created a video to solve this problem in $$$O(N \cdot Log(N))$$$.

https://youtu.be/3VQtW8lnEvQ

Practice Problem