<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 Node:
    def __init__(self, i, j, left = None, right = None, val=0) -> None:
        self.val = val
        self.i, self.j, self.left, self.right = i, j, left, right
        
class Solution:

    def constructTree(self, i, j, nums):
        if i > j:
            return None
        if i == j:
            root = Node(i, i, val = nums[i])
            return root
        if i < j : 
            mid = int((j+i)/2)
            root = Node(i,j)
            left_node = self.constructTree(i,mid,nums)
            right_node = self.constructTree(mid+1, j, nums)
            root.left = left_node
            root.right = right_node
            root.val = left_node.val + right_node.val

            return root

    def updateTree(self, index, val, root):
        if not (root and root.i<=index and root.j>=index):
            return 
        if root and not root.left and not root.right and root.i==index and root.j==index:
            root.val = val
            return

        self.updateTree(index, val, root.left)
        self.updateTree(index, val, root.right)
        root.val = max(root.left.val, root.right.val)

    def sumQueryTree(self, left,right, root):
        mid = int((root.i+root.j)/2)
        if left == root.i and right==root.j:
            return root.val 

        if left > mid:
            res1 = self.sumQueryTree(left, right, 
            root.right)
            return res1 
        elif mid >= right:
            res2 = self.sumQueryTree(left, right, root.left)
            return res2
        else:
            res3 = max(self.sumQueryTree(left, mid, root.left) , self.sumQueryTree(mid+1, right, root.right))
            return res3
         
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        self.nums = nums
        self.root = self.constructTree(0, max(nums),[0 for _ in range(0, max(nums)+1)])
        max_val = 0
        for num in nums:
            prev_max = self.sumQueryTree(max(0,num-k),num-1, self.root)
            cur_max = self.sumQueryTree(num,num, self.root)
            cur_max = max(cur_max, prev_max+1)
            max_val = max(max_val, cur_max)
            self.updateTree(num, cur_max, self.root)
        return max_val
56200