Longest Constrained Increasing Subsequence

Given an integer sequence A of length n and an integer threshold T, find the length of the longest subsequence that is strictly increasing and where the absolute difference between any two consecutive elements does not exceed T. Formally, you need to find the maximum length k of a subsequence \(\{a_1, a_2, \ldots, a_k\}\) such that \(a_1 < a_2 < \cdots < a_k\) and for every \(i = 1, 2, \ldots, k-1\), the inequality \(|a_{i+1} - a_i| \le T\) holds.

This problem combines the concept of the traditional longest increasing subsequence with an additional constraint on the difference between consecutive elements. It requires dynamic programming techniques to efficiently compute the answer even for relatively larger input sizes.

inputFormat

The input is read from standard input (stdin) and consists of three parts:

• The first line contains an integer n, representing the number of elements in the sequence.
• The second line contains n space-separated integers representing the sequence A.
• The third line contains an integer T, indicating the maximum allowed difference between any two consecutive elements in the subsequence.

outputFormat

The output is a single integer printed to standard output (stdout) representing the length of the longest valid subsequence that satisfies the conditions.

6
5 3 4 8 6 7
3

4