<p>You are given an integer array <code>nums</code> and an integer <code>k</code>.</p>

<p>Find the longest subsequence of <code>nums</code> that meets the following requirements:</p>

<ul>
	<li>The subsequence is <strong>strictly increasing</strong> and</li>
	<li>The difference between adjacent elements in the subsequence is <strong>at most</strong> <code>k</code>.</li>
</ul>

<p>Return<em> the length of the <strong>longest</strong> <strong>subsequence</strong> that meets the requirements.</em></p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,1,4,3,4,5,8,15], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,4,5,1,8,12,4,7], k = 5
<strong>Output:</strong> 4
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5], k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        from bisect import bisect_left, bisect_right

        # Coordinate compression to handle large values efficiently
        values = sorted(set(nums))
        mapping = {v: i for i, v in enumerate(values)}

        # Segment Tree implementation for range maximum query and point updates
        class SegmentTree:
            def __init__(self, size):
                self.N = 1
                while self.N < size:
                    self.N <<= 1
                self.size = size
                self.tree = [0] * (2 * self.N)

            def update(self, index, value):
                index += self.N
                self.tree[index] = max(self.tree[index], value)
                while index > 1:
                    index >>= 1
                    self.tree[index] = max(self.tree[index << 1], self.tree[index << 1 | 1])

            def query(self, l, r):
                l += self.N
                r += self.N
                res = 0
                while l < r:
                    if l & 1:
                        res = max(res, self.tree[l])
                        l += 1
                    if r & 1:
                        r -= 1
                        res = max(res, self.tree[r])
                    l >>= 1
                    r >>= 1
                return res

        st = SegmentTree(len(values))
        max_length = 0

        for num in nums:
            idx = mapping[num]
            # Find all previous numbers less than 'num' and within difference 'k'
            left_value = num - k
            right_value = num - 1
            left = bisect_left(values, left_value)
            right = bisect_right(values, right_value)
            if left < right:
                max_prev = st.query(left, right)
            else:
                max_prev = 0
            current_length = max_prev + 1
            st.update(idx, current_length)
            max_length = max(max_length, current_length)

        return max_length
37500