We can use dynamic programming. Let dp[i][val] be the answer using only the first i + 1 elements, and the last element in the subsequence is equal to val.

The only value that might change between dp[i - 1] and dp[i] are dp[i - 1][val] and dp[i][val].

Try using dp[i - 1] and the fact that the second last element in the subsequence has to fall within a range to calculate dp[i][val].

We can use a segment tree to find the maximum value in dp[i - 1] within a certain range.