<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:

        if len(nums) == 1:
            return 1
        
        mxbound = max(nums) * 2

        seg = SegmentTree(0, 2 * mxbound, 1)

        for num in nums:
            lenth = seg.query(num, num, 0, seg.root)
            seg.update(num + 1, num + k, lenth + 1, seg.root)
        return seg.query(0, 2 * mxbound, 0, seg.root) - 1



class TreeNode():
    def __init__(self, lb, rb):
        self.lb = lb
        self.rb = rb

        self.left = None
        self.right = None

        self.val = 1
        self.lazy = -1

        
class SegmentTree:

    def __init__(self, lb, rb, val):
        self.root = TreeNode(lb, rb)

        # self.build(lb, rb, val, self.root)


    def dfs(self, node, s=""):
        if node is None:
            return

        print(s, node.__dict__)
        self.dfs(node.left, s)
        self.dfs(node.right, s)

    def remuli(self, node):
        return 0

    def ryoko(self, node):
        return node.val


    def help(self, lb, rb, val, node, func):

        if node is None:
            return self.remuli(node)

        if lb > node.rb or node.lb > rb:
            if func == self.query:
                return self.remuli(node)
            else:
                return self.ryoko(node)


        if node.left is None:
            lval = self.remuli(node)
        else:
            lval = func(lb, rb, val, node.left)

        if node.right is None:
            rval = self.remuli(node)
        else:
            rval = func(lb, rb, val, node.right)

        mxval = max(lval, rval)

        '''
        if func != self.query:
            node.rmax, node.rttl, node.mxidx = rmax, rttl, mxidx
        '''
 
            
        return mxval


    def build(self, lb, rb, val, node):
        
        if node.lb == node.rb:
            node.val = 0

        else:
            mid = (node.lb + node.rb) // 2
            node.left = TreeNode(node.lb, mid)
            node.right = TreeNode(mid + 1, node.rb)

            self.help(lb, rb, val, node, self.build)

        return self.ryoko(node)
        

    def update(self, lb, rb, val, node):

        if node is None:
            return

        if lb > node.rb or node.lb > rb:
            return

        if lb <= node.lb <= node.rb <= rb:
            self.mergelazy(node, val)
        elif node.lb != node.rb:

            mid = (node.lb + node.rb) // 2

            if node.left is None:
                node.left = TreeNode(node.lb, mid)
                node.right = TreeNode(mid + 1, node.rb)

            self.lazydown(node)

            self.update(lb, rb, val, node.left)
            self.update(lb, rb, val, node.right)


    def mergelazy(self, node, uplazy):
        node.lazy = max(node.lazy, uplazy)

    def lazydown(self, node):
        if node.left:
            self.mergelazy(node.left, node.lazy)

        if node.right:
            self.mergelazy(node.right, node.lazy)

        node.lazy = -1


    def query(self, lb, rb, val, node):

        if node is None:
            return self.muli(node)

        if lb > node.rb or node.lb > rb:
            return self.remuli(node)

        if node.left is None and node.right is None:
            node.val = max(node.val, node.lazy)
            node.lazy = -1
            return node.val

        self.lazydown(node)

        return self.help(lb, rb, 0, node, self.query)
59600