Find the longest contigous subsequence where each pair's difference is at most p
You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x_i,\ldots,x_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x_i,\ldots,x_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity
$$\min(x_i,\ldots,x_{i+2^{\ell+1}-1}) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}),\min(x_{i+2^\ell},\ldots,x_{i+2^\ell+2^{\ell}-1})\bigr). $$
Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log_2 (j-i+1) \rceil$ in constant time. Then
$$
\min(x_i,\ldots,x_j) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}), \min(x_{j-2^\ell+1},\ldots,x_j)\bigr).
$$

For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x_\ell,\ldots,x_i) \geq x_i-p$ and the minimal $r \geq i$ such that $\min(x_i,\ldots,x_r) \geq x_i-p$. Thus $x_\ell,\ldots,x_r$ is the largest interval satisfying your constraint in which $x_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.