Strip
Alexandra has a paper strip with n numbers on it. Let's call them ai from left to right.Now Alexandra wants to split it into some pieces (possibly 1). For each piece of strip, it must satisfy: Each piece should contain at least l numbers. The difference between the maximal and the minimal number on the piece should be at most s.Please help Alexandra to find the minimal number of pieces meeting the condition above.
For the first sample, we can split the strip into 3 pieces: [1, 3, 1], [2, 4], [1, 2].For the second sample, we can't let 1 and 100 be on the same piece, so no solution exists.
The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).The second line contains n integers ai separated by spaces ( - 109 ≤ ai ≤ 109).
Output the minimal number of strip pieces.If there are no ways to split the strip, output -1.
from collections import deque
from typing import List
import sys

def get(arr: List[int], index):
    if index < 0:
        return 0
    return arr[index]

def Solution(n: int, s: int, l: int, strip: List[int]):
    INF = sys.maxsize
    dp = [INF] * n
    minQueue = deque()
    maxQueue = deque()
    j = 0
    for i in range(n):
        current = strip[i]
        while len(minQueue) > 0 and current < minQueue[-1][1]:
            minQueue.pop()
        minQueue.append((i, current))
        while len(maxQueue) > 0 and current > maxQueue[-1][1]:
            maxQueue.pop()
        maxQueue.append((i, current))
        while j < i:
            while len(minQueue) > 0 and minQueue[0][0] < j:
                minQueue.popleft()
            while len(maxQueue) > 0 and maxQueue[0][0] < j:
                maxQueue.popleft()
            min = minQueue[0][1]
            max = maxQueue[0][1]
            diff = max - min
            if diff > s:
                j += 1
            elif get(dp, j - 1) == INF:
                j += 1
            else:
                break
        if i - j + 1 >= l and get(dp, j - 1) != INF:
            dp[i] = 1 + get(dp, j - 1)
    if dp[n - 1] == INF:
        return -1
    else:
        return dp[n - 1]
(n, s, l) = map(int, input().split())
strip = list(map(int, input().split()))
print(Solution(n=n, s=s, l=l, strip=strip))
import heapq
import sys

class Data:

    def __init__(self, val, del_val):
        self.val = val
        self.del_val = del_val

class MinQueue:

    def __init__(self):
        self.data = []

    def push(self, v):
        d = Data(v, 1)
        while self.data and d.val <= self.data[-1].val:
            d.del_val += self.data.pop().del_val
        self.data.append(d)

    def pop(self):
        if self.data[0].del_val > 1:
            self.data[0].del_val -= 1
        else:
            self.data.pop(0)

    def top(self):
        return self.data[0].val

class MaxQueue:

    def __init__(self):
        self.data = []

    def push(self, v):
        d = Data(v, 1)
        while self.data and d.val >= self.data[-1].val:
            d.del_val += self.data.pop().del_val
        self.data.append(d)

    def pop(self):
        if self.data[0].del_val > 1:
            self.data[0].del_val -= 1
        else:
            self.data.pop(0)

    def top(self):
        return self.data[0].val

def cf487b():
    (n, max_d, min_l) = map(int, input().split())
    small = MinQueue()
    big = MaxQueue()
    dp_mq = MinQueue()
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    a = list(map(int, input().split()))
    for (i, v) in enumerate(a, 1):
        small.push(v)
        big.push(v)
        if i < min_l:
            continue
        dp_mq.push(dp[i - min_l])
        while dp_mq.data and big.top() - small.top() > max_d:
            small.pop()
            big.pop()
            dp_mq.pop()
        if dp_mq.data:
            dp[i] = dp_mq.top() + 1
    if dp[n] >= float('inf'):
        dp[n] = -1
    print(dp[n])
if __name__ == '__main__':
    cf487b()
from collections import deque
''

def solve(N, S, L, A):
    (qmax, qmin) = (deque(), deque())
    F = [N + 1] * (N + 1)
    F[0] = 0
    q = deque()
    j = 0
    for i in range(1, N + 1):
        x = A[i]
        while qmax and A[qmax[-1]] <= x:
            qmax.pop()
        qmax.append(i)
        while qmin and A[qmin[-1]] >= x:
            qmin.pop()
        qmin.append(i)
        while j < i and qmax and qmin and (A[qmax[0]] - A[qmin[0]] > S):
            while qmax and qmax[0] <= j:
                qmax.popleft()
            while qmin and qmin[0] <= j:
                qmin.popleft()
            j += 1
        if i >= L:
            while q and q[-1][1] >= F[i - L]:
                q.pop()
            q.append((i - L, F[i - L]))
        while q and q[0][0] < j - 1:
            q.popleft()
        if q:
            F[i] = q[0][1] + 1
    return F[-1] if F[-1] <= N else -1
if __name__ == '__main__':
    (N, S, L) = (int(_) for _ in input().split())
    A = [0] + [int(_) for _ in input().split()]
    print(solve(N, S, L, A))