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

import math
from typing import List


class SegmentTree:
    def __init__(self, n):
        self._n = n
        self._tree = [0] * (4 * n)

    def query(self, i, j):
        def _query(node, query_i, query_j, left, right):
            if query_i <= left and right <= query_j:
                return self._tree[node]
            elif query_j < left or right < query_i:
                return -math.inf

            mid = (left + right) // 2
            return max(_query(node * 2 + 1, query_i, query_j, left, mid),
                       _query(node * 2 + 2, query_i, query_j, mid + 1, right))

        return _query(node=0, query_i=i, query_j=j, left=0, right=self._n - 1)

    def update(self, a, val):
        def _update(node, left, right):
            if not (left <= a <= right):
                return

            if left == right:
                self._tree[node] = max(self._tree[node], val)
                return

            mid = (left + right) // 2
            _update(node * 2 + 1, left, mid)
            _update(node * 2 + 2, mid + 1, right)
            self._tree[node] = max(self._tree[node * 2 + 1],
                                   self._tree[node * 2 + 2])

        _update(node=0, left=0, right=self._n - 1)

    def max_value(self):
        return self._tree[0]


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        segment_tree = SegmentTree(max(nums) + 1)
        for a in nums:
            i, j = max(0, a - k), a - 1
            q = segment_tree.query(i, j)
            segment_tree.update(a, q + 1)
        return segment_tree.max_value()
46500