# Longest Subsequence with Bounded Differences
## Problem Statement
Given an array $a$ of $n$ integers and an integer $d$, find the length of the longest subsequence $s_1, s_2, \ldots, s_k$ such that for every consecutive pair of elements $s_j$ and $s_{j+1}$ in the subsequence, the absolute difference $|s_j - s_{j+1}|$ is less than or equal to $d$.
Recall that a subsequence is formed by deleting zero or more elements from the original array while maintaining the relative order of the remaining elements. Specifically, if $s_j = a_p$ and $s_{j+1} = a_q$, then it must hold that $p < q$.
## Input Format
- The first line contains a single integer $n$ ($1 \le n \le 10^5$), representing the number of elements in the array.
- The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), representing the elements of the array.
- The third line contains a single integer $d$ ($1 \le d \le 10^9$), representing the maximum allowed absolute difference.
## Output Format
Output a single integer representing the length of the longest valid subsequence that satisfies the given condition.
## Sample Test Cases
### Sample Input 1
```
6
3 5 7 1 2 1
2
```
### Sample Output 1
```
4
```
### Sample Input 2
```
5
10 20 5 15 30
5
```
### Sample Output 2
```
2
```
## Constraints
- $1 \le n \le 10^5$
- $-10^9 \le a_i \le 10^9$
- $1 \le d \le 10^9$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
For Sample Input 1: The array is $a = [3, 5, 7, 1, 2, 1]$ and $d = 2$.
One of the longest valid subsequences is $[3, 1, 2, 1]$. The elements are $a_1=3, a_4=1, a_5=2, a_6=1$. Their original indices are $1 < 4 < 5 < 6$.
Let's check the absolute differences between consecutive elements:
- $|3 - 1| = 2 \le 2$
- $|1 - 2| = 1 \le 2$
- $|2 - 1| = 1 \le 2$
All differences satisfy the condition, and the length of this subsequence is $4$.
For Sample Input 2: The array is $a = [10, 20, 5, 15, 30]$ and $d = 5$.
One of the longest valid subsequences is $[10, 5]$. The elements are $a_1=10, a_3=5$. Their original indices are $1 < 3$.
Let's check the absolute difference: $|10 - 5| = 5 \le 5$.
This subsequence has length $2$. Another valid subsequence is $[20, 15]$ (using $a_2=20, a_4=15$). Any subsequence of length $3$ or more would violate the difference constraint. For example, extending $[10, 5]$ with an element $a_k$ where $k > 3$: $a_4=15 \implies |15-5|=10 > 5$; $a_5=30 \implies |30-5|=25 > 5$. Thus, the maximum length is $2$.
Loading problem statement...