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






















class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * 2 * n

    def query(self, l, r):
        # l, r are the range of the query
        # the goal is to find the maximum value within the query range [l, r)
        # for idx i, its left node is 2*i, right node is 2*i+1. 
        # If the range [l, r) is complete (l is left node, r is left node), looking up max value will be simply done by searching its parents. 
        #   Why r must be left node? Think about the range [l, r). It means l is included, but r is not included. 
        #   If r is the left node, that means r-1 is right node, and the range [l, r-1] will be from left node to the right node, becoming complete. 
        #   So, if l is not left, index l must be adjusted. And if r is not left, index r must be adjusted. 
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                # l is right node now. 
                # So, adjust l to be left node
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                # r is right node now. 
                # So, adjust r to be left node. 
                r -= 1
                ans = max(ans, self.tree[r])
                
            r //= 2
            l //= 2
        return ans

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = max(self.tree[i*2], self.tree[i*2+1])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = max(nums)
        ans = 1
        segTree = SegmentTree(n)
        for num in nums:
            num -= 1 # think about the index / value difference by 1. 
            # num starts from 1. So, num=1 will be corresponding to idx=0. 
            premax = segTree.query(max(0, num-k), num)
            ans = max(ans, premax+1) # +1 because the current number should be included
            segTree.update(num, premax+1)

        return ans
























class  SegmentTree:
    def __init__(self, size):
        self.tree = [0] * size * 2
        self.size = size
    
    def query(self, l, r):
        # Find the maximum value in [l, r)
        l += self.size
        r += self.size

        ans = 0
        while l < r:
            if l % 2 == 1:
                # if l is right node
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                # if r is right node
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return max(ans, self.tree[l]) 

    def update(self, i, val):
        i += self.size
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = max(self.tree[i*2], self.tree[i*2+1])
        



class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        ans = 1
        st = SegmentTree(max(nums))
        for i, num in enumerate(nums):
            num -= 1
            premax = st.query(max(0, num-k), num)
            ans = max(ans, premax+1)
            st.update(num, premax+1)
        return ans



























class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_len = 1
        #dp = [1] * (max(nums)+1)
        dp = {}
        for num in nums:
            dp[num] = 1

        for i1 in range(len(nums)):
            for i2 in range(i1):
                n1, n2 = nums[i1], nums[i2]
                if n1 > n2 and n1 - n2 <= k:
                    dp[n1] = max(dp[n1], dp[n2] + 1)
                    max_len = max(max_len, dp[n1])
        return max_len


class SegmentTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * size * 2

    def query(self, l, r):
        l += self.size
        r += self.size
        ans = 0
        while l < r:
            if l % 2 == 1:
                # right
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                # right
                ans = max(ans, self.tree[r-1])
                r -= 1
            r //= 2
            l //= 2
        return ans

    def update(self, idx, val):
        idx += self.size
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        segTree = SegmentTree(size=max(nums))
        ans = 1
        for num in nums:
            num -= 1
            q = segTree.query(max(0, num-k), num)
            ans = max(ans, q+1)
            segTree.update(num, q+1)
        return ans






































class SegmentTree:
    def __init__(self, size):
        self.tree = [0] * size * 2
        self.size = size

    def query(self, l, r) -> int:
        '''
        given query range of [l, r), return the maximum value. 
        for node k, k%2==0--> left node, 1--> right node.
        '''
        l += self.size
        r += self.size
        ans = 0
        while l < r:
            if l % 2 == 1:
                # if l is in the right node
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                # if r is in the right node
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return ans
    
    def update(self, idx, val) -> None:
        idx += self.size
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])



class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        ans = 1
        for idx, num in enumerate(nums):
            num -= 1
            max_len = st.query(max(0, num-k), num) + 1
            st.update(num, max_len)
            ans = max(ans, max_len)
        print(st.tree)
        return ans

























class SegmentTree:
    def __init__(self, size):
        self.tree = [0] * size * 2
        self.size = size

    def query(self, l, r):
        # given the range of [l, r), return the max value
        l += self.size
        r += self.size
        ans = 0
        while l < r:
            if l % 2 == 1:
                # l is currently right node
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return ans
    
    def update(self, idx, val):
        idx += self.size
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[2*idx+1], self.tree[2*idx])
        


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        ans = 1
        for i, num in enumerate(nums):
            num -= 1
            prefix = st.query(max(0, num-k), num) + 1
            ans = max(ans, prefix)
            st.update(num, prefix)
        return ans






















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * 2 * n
        self.n = n

    def query(self, l, r):
        # return max value within query range [l, r)
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            r //= 2
            l //= 2
        return ans
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        ans = 0
        for num in nums:
            num -= 1
            pref = st.query(max(0, num-k), num) + 1
            ans = max(ans, pref)
            st.update(num, pref)
        return ans





















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n

    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(self.tree[l], ans)
                l += 1
            if r % 2 == 1:
                ans = max(self.tree[r-1], ans)
                r -= 1
            l //= 2
            r //= 2
        return ans

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(n=max(nums))
        ans = 0
        for num in nums:
            num -= 1
            ans_tmp = st.query(max(0, num-k), num) + 1
            ans = max(ans, ans_tmp)
            st.update(num, ans_tmp)
        return ans






















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n

    def query(self, l, r) -> int:
        # given query range [l, r), return max
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                # # l is right node
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                # r is right node:
                ans = max(ans, self.tree[r-1])
                r -= 1
            r //= 2
            l //= 2
        return ans

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[2*idx], self.tree[2*idx+1])


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        max_len = 0
        for num in nums:
            num -= 1
            curr_len = st.query(max(0, num-k), num) + 1
            max_len = max(max_len, curr_len)
            st.update(num, curr_len)
        return max_len
























class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n

    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            r //= 2
            l //= 2
        return ans
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[2*idx], self.tree[2*idx+1])


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        ans = 0
        for num in nums:
            num-= 1
            ln = st.query(max(0, num-k), num) + 1
            st.update(num, ln)
            ans = max(ans, ln)
        return ans






















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n
    
    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            r //= 2
            l //= 2
        return ans
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])
        
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))

        ans = 0
        for num in nums:
            num -= 1
            ln = st.query(max(0, num-k), num) + 1
            st.update(num, ln)
            ans = max(ans, ln)
        return ans






















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n
    
    def query(self, l, r):
        l += self.n
        r += self.n
        max_ln = 0
        while l < r:
            if l % 2 == 1:
                max_ln = max(max_ln, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                max_ln = max(max_ln, self.tree[r])
            l //= 2
            r //= 2
        return max_ln
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        ans = 0
        for num in nums:
            num -= 1
            ln = st.query(max(0, num-k), num) + 1
            ans = max(ans, ln)
            st.update(num, ln)
        return ans




















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n
    
    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return ans

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        max_ln = 0
        for i, num in enumerate(nums):
            num -= 1
            ln = st.query(max(0, num-k), num)
            max_ln = max(max_ln, ln+1)
            st.update(num, ln+1)
        return max_ln



















class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * 2 * n
    
    def query(self, p1, p2):
        p1 += self.n
        p2 += self.n
        max_val = 0
        while p1 < p2:
            if p1 % 2 == 1:
                max_val = max(max_val, self.tree[p1])
                p1 += 1
            if p2 % 2 == 1:
                max_val = max(max_val, self.tree[p2-1])
                p2 -= 1
            p1 //= 2
            p2 //= 2
        return max_val
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])
        

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums))
        max_ln = 0
        for num in nums:
            num -= 1
            ln = st.query(max(0, num-k), num) + 1
            max_ln = max(max_ln, ln)
            st.update(num, ln)
        return max_ln


















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n
    
    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return ans

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])
        

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums)+1)
        max_ln = 0
        for idx, num in enumerate(nums):
            #num -= 1
            ln = st.query(max(0, num-k), num)
            max_ln = max(max_ln, ln+1)
            st.update(num, ln+1)
        return max_ln























class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n

    def query(self, l, r):
        l += self.n
        r += self.n
        max_val = 0
        while l < r:
            if l % 2 == 1:
                max_val = max(max_val, self.tree[l])
                l += 1
            if r % 2 == 1:
                max_val = max(max_val, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return max_val
    
    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])
        

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums)+1)
        max_ln = 0
        for idx, num in enumerate(nums):
            ln = st.query(max(0, num-k), num) + 1
            max_ln = max(max_ln, ln)
            st.update(num, ln)
        return max_ln
















class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * n * 2
        self.n = n
    
    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l % 2 == 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r % 2 == 1:
                ans = max(ans, self.tree[r-1])
                r -= 1
            l //= 2
            r //= 2
        return ans

    def update(self, val, idx):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            idx //= 2
            self.tree[idx] = max(self.tree[idx*2], self.tree[idx*2+1])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        st = SegmentTree(max(nums)+1)
        max_ln = 0
        for idx, num in enumerate(nums):
            ln = st.query(max(0, num-k), num) + 1
            max_ln = max(max_ln, ln)
            st.update(ln, num)
        return max_ln
28900