<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 Segment:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*n
    def query(self, left, right, idx, qleft, qright):
        if qleft > qright:
            return 0
        if qleft <= left and right <= qright:
            return self.tree[idx]
        if qleft > right or qright < left:
            return 0
        
        mid = (left + right)//2
        
        resleft = self.query(left, mid, 2*idx+1, qleft, min(mid, qright))
        
        resright = self.query(mid+1, right, 2*idx+2, max(qleft, mid), qright)
        return max(resleft, resright)
    
    def update(self, left, right, idx, pos, val):
        if left==right:
            self.tree[idx] = val
            return
        mid = (left+right)//2
        if pos <= mid:
            self.update(left, mid, 2*idx+1, pos, val)
        else:
            self.update(mid+1, right, 2*idx+2, pos, val)

        self.tree[idx] = max(self.tree[2*idx+1], self.tree[2*idx+2])
        return
                             
        

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        Set = sorted(list(set(nums)))
        Set_idx = {x: i for i, x in enumerate(Set)}
        comp = self.compress(Set_idx, nums)
        n = len(Set)
        seg = Segment(4*n)
        for i in range(len(nums)):
            threshold = nums[i] - k
            lo, hi = 0, comp[i]
            res = comp[i]
            while lo <= hi:
                mid = (lo+hi)//2
                if Set[mid]>= threshold:
                    res = mid
                    hi = mid-1
                else:
                    lo = mid+1
             
            sublongest = seg.query(0, n-1, 0, res, comp[i]-1)
            seg.update(0, n-1, 0, comp[i], sublongest+1)
        return max(seg.tree)
    def compress(self, Set_idx, arr):
        res = [0]*len(arr)
        for i in range(len(arr)):
            res[i] = Set_idx[arr[i]]
        return res
37700