<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 _MaxSubarrayLengthSegmentTree:
    def __init__(self, max_number):
        self.__max_number = max_number
        self.__tree = [0] * 2 ** (ceil(log2(max_number + 1)) + 1)

    @property
    def max_length(self):
        return max(self.__tree)

    def get_max_length(self, target_interval_left, target_interval_right):
        return self.__get_max_length(0, 1, self.__max_number, target_interval_left, target_interval_right)

    def __get_max_length(self, vertex, vertex_interval_left, vertex_interval_right, target_interval_left, target_interval_right):
        if vertex_interval_left > target_interval_right or vertex_interval_right < target_interval_left:
            return 0

        if vertex_interval_left >= target_interval_left and vertex_interval_right <= target_interval_right:
            return self.__tree[vertex]

        vertex_interval_middle = (vertex_interval_left + vertex_interval_right) // 2

        return max(
            self.__get_max_length(2 * vertex + 1, vertex_interval_left, vertex_interval_middle, target_interval_left, min(vertex_interval_middle, target_interval_right)),
            self.__get_max_length(2 * vertex + 2, vertex_interval_middle + 1, vertex_interval_right, max(vertex_interval_middle + 1, target_interval_left), target_interval_right),
        )

    def update(self, position, length):
        return self.__update(0, 1, self.__max_number, position, length)

    def __update(self, vertex, vertex_interval_left, vertex_interval_right, position, length):
        if vertex_interval_left > position or vertex_interval_right < position:
            return

        if vertex_interval_left >= position and vertex_interval_right <= position:
            self.__tree[vertex] = max(length, self.__tree[vertex])

            return

        vertex_interval_middle = (vertex_interval_left + vertex_interval_right) // 2
        left_vertex = 2 * vertex + 1
        right_vertex = left_vertex + 1
        self.__update(left_vertex, vertex_interval_left, vertex_interval_middle, position, length)
        self.__update(right_vertex, vertex_interval_middle + 1, vertex_interval_right, position, length)
        self.__tree[vertex] = max(self.__tree[left_vertex], self.__tree[right_vertex])

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_number = max(nums)
        max_subarray_length_segment_tree = _MaxSubarrayLengthSegmentTree(max_number)

        for number in reversed(nums):
            end_number = min(number + k, max_number)
            max_length = max_subarray_length_segment_tree.get_max_length(number + 1, end_number) + 1
            max_subarray_length_segment_tree.update(number, max_length)

        return max_subarray_length_segment_tree.max_length

28000