<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 query(ql, qr, pos, L, R):
            if ql<=L and qr>=R:
                return tree[pos] # f([L, R])
            M = (L+R)//2
            ans = 0 # should be set to -inf if g=MAX
            if qr > M:
                rans = query(ql, qr, 2*pos+2, M+1, R)
                ans = max(ans, rans)
            if ql <= M:
                lans = query(ql, qr, 2*pos+1, L, M)
                ans = max(ans, lans)
            return ans
                
        # point update 
        def update(val, target, pos, L, R):
            #print(target, L, R)
            if L>R:
                return
            if L==R:
                #print(val, target, pos, L, R)
                tree[pos] = val 
                return
            M = (L+R)//2
            if target <= M:
                update(val, target, 2*pos+1, L, M)
                tree[pos] = max(tree[2*pos+1], tree[2*pos + 2])
                return
            if target > M:
                update(val, target, 2*pos+2, M+1, R)
                tree[pos] = max(tree[2*pos+1], tree[2*pos + 2])
                return

        def init(array):
            N = len(array)
            global tree
            tree = [0] * (4 * N)
            for i, num in enumerate(array):
                update(num, i, 0, 0, N-1)

        N = len(nums)
        H = max(nums) + 1
        tree = [0] * (4*H)

        for i, num in enumerate(nums):
            newval = query(max(num-k, 0), max(num-1, 0), 0, 0, H-1) + 1
            update(newval, num, 0, 0, H-1)
        
        return max(tree)
57600