<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 SegmentTree:
    
    def __init__(self, A: list[int]):
        n = len(A)
        closest_2_power = math.ceil(math.log2(n))
        # pad
        A += [0] * ((2 << (closest_2_power-1)) - n)
        
        self._closest_2_power = closest_2_power
        self._arr = A
        self.tree = [0] * (2*len(A) - 1)
        
        self._build_segtree(0, 0, len(self._arr) - 1)
        
    
    # Building maximum query segment tree
    def _build_segtree(self, tree_index, left, right):
        # Leaf node
        if left == right:
            self.tree[tree_index] = self._arr[left]
            return self.tree[tree_index]
    
        mid = left + (right - left) // 2
        left_seg = self._build_segtree(tree_index * 2 + 1, left, mid)
        right_seg = self._build_segtree(tree_index * 2 + 2, mid + 1, right)
        return max(left_seg, right_seg)
    
    def query(self, query_left, query_right, tree_index = None, seg_left = None, seg_right = None):
        # default values
        if seg_left is None:
            seg_left = 0
        if seg_right is None:
            seg_right = len(self._arr) - 1
        if tree_index is None:
            tree_index = 0
        
        # if segment interval is fully contained by query
        if query_left <= seg_left and query_right >= seg_right:
            return self.tree[tree_index]
        
        # if not contained
        if query_right < seg_left or query_left > seg_right:
            return 0
        
        # else divide and conquer both sides
        mid = seg_left + (seg_right - seg_left) // 2
        left_seg = self.query(query_left, query_right, tree_index*2+1, seg_left, mid)
        right_seg = self.query(query_left, query_right, tree_index*2+2, mid + 1, seg_right)
        return max(left_seg, right_seg)
    
    
    def update(self, original_index, new_value):
        first_leaf_index = (2 ** self._closest_2_power) - 1
        tree_index = first_leaf_index + original_index
        self.tree[tree_index] = new_value
        
        # update parent interval
        parent_index = (tree_index - 1) // 2
        while parent_index >= 0:
            self.tree[parent_index] = max(self.tree[parent_index], new_value)
            parent_index = (parent_index - 1) // 2

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        MAX = max(nums)
        A = [0] * (MAX + 1)
        
        seg_tree = SegmentTree(A)
        ans = 0
        
        for v in nums:
            max_interval_sum = seg_tree.query(max(0, v-k), v-1)
            v_lis = max(1, 1 + max_interval_sum)
            seg_tree.update(v, v_lis)
            ans = max(ans, v_lis)
        return ans

27800