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

from sortedcontainers import SortedList
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        ds = [SortedList([nums[0]])] # list of SortedList
        for i in range(1, len(nums)):
            if nums[i] > ds[-1][-1] + k or nums[i] < ds[0][0]: 
                # out of range-k of top or less than bottom
                pos = 0 # reset to 0
            else: # perform binary search on the min of each pos
                s, e = 0, len(ds)-1
                while s < e:
                    m = (s + e)//2
                    if nums[i] >= ds[m][0]:
                        s = m + 1
                    else:
                        e = m - 1
                pos = s - 1 if nums[i] < ds[s][0] else s
            
            # find the nearest element within k from nums[i] at pos
            j = ds[pos].bisect_left(nums[i]) - 1
            if j != -1 and ds[pos][j] >= nums[i] - k: 
                # within range-k -> push to pos + 1
                if pos + 1 >= len(ds):
                    ds.append(SortedList([nums[i]]))
                else: 
                    ds[pos + 1].add(nums[i])
            else: # out of range-k -> pos
                ds[pos].add(nums[i])
        
        # the complexity of this algo is Nlog^2(N)
        return len(ds)
69200