<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 update(self, tree, val, i, start, end, si):
        if start == end:
            return max(val, tree[si])

        mid = (start + end)//2
        if i <= mid:
            tree[2*si + 1] = self.update(tree, val, i, start, mid, 2*si + 1)
        else:
            tree[2*si+2] = self.update(tree, val, i, mid+1, end, 2*si + 2)
        
        tree[si] = max(tree[2*si + 1], tree[2*si + 2])

        return tree[si]
        
    def getMax(self, tree, start, end, qs, qe, si):
        if qs > end or qe < start:
            return -sys.maxsize
        
        if start >= qs and end <= qe:
            return tree[si]
        

        mid = (start + end)//2

        res = max(self.getMax(tree, start, mid, qs, qe, 2*si+1), self.getMax(tree, mid + 1, end, qs, qe, 2*si+2))

        return res



    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_num = max(nums)
        max_n = 10**5+1
        tree = [0 for i in range(5*max_n)]
        
        res = -1
        max_len = 0
        for i in range(n):
            left = max(0, nums[i] - k)
            right = nums[i] - 1
            max_len = 1 + self.getMax(tree, 0, max_n-1, left, right, 0)
            res = max(res, max_len)
            self.update(tree, max_len, nums[i], 0, max_n-1, 0)

        print(tree[:15])

        return res

        
30600