<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:
        # dp[i][val] = LIS till i and last elem is val
        # dp[i][val] = max(dp[i-1][j] + 1) val-k <= j < val
        n = len(nums)
        max_val = max(nums) + 1
        t = [0 for _ in range(4*max_val)]
        dp = [0 for _ in range(max_val)]
        
        def query(tl, tr, l, r, v):
            if l > r:
                return 0
            if tl == l and tr == r:
                return t[v]
            mid = (tl + tr) // 2
            return max(
                query(tl, mid, l, min(mid, r), v*2),
                query(mid+1, tr, max(l, mid+1), r, v*2 +1)
            )
        
        def update(tl, tr, pos, val, v):
            if tl == tr:
                t[v] = val
            else:
                mid = (tl + tr) // 2
                if pos <= mid:
                    update(tl, mid, pos, val, v*2)
                else:
                    update(mid+1, tr, pos, val, v*2+1)
                t[v] = max(t[v*2], t[v*2+1])
        
        for i in range(n):
            dp[nums[i]] = query(
                0, 
                max_val-1, 
                max(0, nums[i]-k), 
                min(max_val-1, nums[i]-1), 
                1
            ) + 1
            update(0, max_val-1, nums[i], dp[nums[i]], 1)
        
        return max(dp)

58500