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

    def __init__(self, n: int):
        self.size = 1 << (n-1).bit_length()
        self.size = 2 * self.size
        self.arr = [0] * self.size

    def only_increase(self, index, value):
        p = 1
        index = 2*index+1
        while index != self.size:
            if value <= self.arr[index]:
                return
            self.arr[index] = value

            p2 = 2 * p
            index += p
            if index & -index != p2:   # lsb(index+p)
                index -= p2

            p = p2

    def max_between(self, a, b):
        a = 2*a + 1
        b = 2*b + 1

        p = 1
        current_max = self.arr[a]
        while a < b:
            p2 = p * 2
            if (a-p) & (p-a) == p2:  # lsb(a-p)
                if current_max < self.arr[a]:
                    current_max = self.arr[a]
                a += p2
                if a == b:
                    break

            if (b+p) & (-b-p) == p2:  # lsb(b+p)
                if current_max < self.arr[b]:
                    current_max = self.arr[b]
                b -= p2

            a += p
            b -= p

            p = p2

        if current_max < self.arr[a]:
            current_max = self.arr[a]

        return current_max


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        sorted_nums = sorted(set(nums))
        num_to_index = dict()
        for index, num in enumerate(sorted_nums):
            num_to_index[num] = index
        max_tree = FullBinaryTree_Max(len(num_to_index))

        total_max = 0

        for num in nums:
            num_index = num_to_index[num]
            upper = num_index
            lower = num_index - k
            if lower < 0:
                lower = 0
            if sorted_nums[lower] <= num - k:
                # we now have that sorted_nums[lower] <= num-k < sorted_nums[upper] = num
                while lower < upper-1:
                    mid = (lower + upper)//2
                    if num-k < sorted_nums[mid]:
                        upper = mid
                    else:
                        lower = mid

            if sorted_nums[lower] < num-k:
                lower += 1

            previous_max = 0 if num_index <= lower else max_tree.max_between(lower, num_index-1)
            max_tree.only_increase(num_index, previous_max + 1)
            if total_max < previous_max + 1:
                total_max = previous_max + 1

        return total_max


37400