<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:
        def mx(a, fr, to):
            res = a[fr]
            i = fr + 1
            while i < to:
                if a[i] > res:
                    res = a[i]
                i += 1
            return res

        class RangeTree:
            def __init__(self, left, right):
                self.l = left
                self.r = right
                self.v = 0
                self.l_ch = None
                self.r_ch = None
                if right - left < 4:
                    self.vals = [0] * (right - left)
                else:
                    self.vals = []

            def split(self):
                mid = (self.l + self.r) // 2
                self.l_ch = RangeTree(self.l, mid)
                self.r_ch = RangeTree(mid, self.r)        

            def set(self, x, val):
                if self.vals:
                    self.vals[x - self.l] = val
                    self.v = max(self.v, val)
                    return
                if not self.l_ch:
                    self.split()
                if x < self.l_ch.r:
                    self.l_ch.set(x, val)
                    self.v = max(self.v, self.l_ch.v)
                else:
                    self.r_ch.set(x, val)
                    self.v = max(self.v, self.r_ch.v)

            def max(self, left, right):
                if left <= self.l and self.r <= right:
                    return self.v
                if self.r <= left or right <= self.l:
                    return 0
                if self.vals:
                    lb = max(0, left - self.l)
                    rb = min(len(self.vals), right - self.l)
                    return mx(self.vals, lb, rb)
                if not self.l_ch:
                    return 0
                return max(self.l_ch.max(left, right), self.r_ch.max(left, right))

        rt = RangeTree(min(nums), max(nums) + 1)
        for x in nums:
            rt.set(x, rt.max(x - k, x) + 1)
        return rt.v

40200