#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline string toString(T a) {
  ostringstream os("");
  os << a;
  return os.str();
}
template <typename T>
inline long long toLong(T a) {
  long long res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline int toInt(T a) {
  int res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline double toDouble(T a) {
  double res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline T SQ(T a) {
  return a * a;
}
template <typename T>
inline T GCD(T a, T b) {
  if (b == 0)
    return a;
  else
    return GCD(b, a % b);
}
template <typename T>
inline T LCM(T a, T b) {
  long long res = a * b;
  res /= GCD(a, b);
  return res;
}
template <typename T>
inline unsigned long long BIGMOD(T a, T b, T m) {
  if (b == 0)
    return 1;
  else if (b % 2 == 0)
    return SQ(BIGMOD(a, b / 2, m)) % m;
  else
    return (a % m * BIGMOD(a, b - 1, m)) % m;
}
template <typename T>
inline vector<string> PARSE(T str) {
  vector<string> res;
  string s;
  istringstream os(str);
  while (os >> s) res.push_back(s);
  return res;
}
template <typename T>
inline unsigned long long DIST(T A, T B) {
  unsigned long long res =
      (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
  return res;
}
template <typename T>
inline long long CROSS(T A, T B, T C) {
  return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
template <typename T>
inline double cosAngle(T a, T b, T c) {
  double res = a * a + b * b - c * c;
  res = res / (2 * a * b);
  res = acos(res);
  return res;
}
template <typename T>
inline T POWER(T base, int po) {
  T res = 1;
  if (base == 0) return 0;
  for (int i = (0); i < (po); i++) res *= base;
  return res;
}
template <typename T>
inline bool IS_ON(T mask, T pos) {
  return mask & (1 << pos);
}
template <typename T>
inline int OFF(T mask, T pos) {
  return mask ^ (1 << pos);
}
template <typename T>
inline int ON(T mask, T pos) {
  return mask | (1 << pos);
}
template <typename T>
inline bool INSIDE_GRID(int R, int C, int ro, int clm) {
  if (R >= 0 && C >= 0 && R < ro && C < clm) return 1;
  return 0;
}
struct Z {
  int boro, choto;
  Z(){};
};
Z tree[4 * 100005];
int inp[100005];
int L[100005];
int seg[4 * 100005];
int dp[100005];
int n, l, s;
void insert1(int cur, int st, int ed) {
  if (st == ed) {
    tree[cur].choto = inp[st];
    tree[cur].boro = inp[st];
    return;
  }
  int mid, lft, rgt;
  mid = (st + ed) / 2;
  lft = 2 * cur, rgt = lft + 1;
  insert1(lft, st, mid);
  insert1(rgt, mid + 1, ed);
  tree[cur].choto =
      (tree[lft].choto > tree[rgt].choto ? tree[rgt].choto : tree[lft].choto);
  tree[cur].boro =
      (tree[lft].boro > tree[rgt].boro ? tree[lft].boro : tree[rgt].boro);
}
pair<int, int> query1(int cur, int st, int ed, int x, int y) {
  if (st == x && ed == y) {
    return make_pair(tree[cur].boro, tree[cur].choto);
  }
  int mid, lft, rgt;
  mid = (st + ed) / 2;
  lft = cur * 2, rgt = lft + 1;
  if (y <= mid)
    return query1(lft, st, mid, x, y);
  else if (x > mid)
    return query1(rgt, mid + 1, ed, x, y);
  else {
    pair<int, int> a = query1(lft, st, mid, x, mid);
    pair<int, int> b = query1(rgt, mid + 1, ed, mid + 1, y);
    a.first = max(a.first, b.first);
    a.second = min(a.second, b.second);
    return a;
  }
}
int bs(int x) {
  int best = x, low = 1, high = x, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    pair<int, int> a = query1(1, 1, n, mid, x);
    if (a.first - a.second <= s) {
      best = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  return best;
}
void insert(int cur, int st, int ed) {
  if (st == ed) {
    seg[cur] = INT_MAX / 3;
    return;
  }
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  insert(lft, st, mid);
  insert(rgt, mid + 1, ed);
  seg[cur] = (seg[lft] > seg[rgt] ? seg[rgt] : seg[lft]);
}
int answer(int cur, int st, int ed, int x, int y) {
  if (st == x && ed == y) return seg[cur];
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  if (y <= mid)
    return answer(lft, st, mid, x, y);
  else if (x > mid)
    return answer(rgt, mid + 1, ed, x, y);
  else
    return (answer(lft, st, mid, x, mid) > answer(rgt, mid + 1, ed, mid + 1, y)
                ? answer(rgt, mid + 1, ed, mid + 1, y)
                : answer(lft, st, mid, x, mid));
}
void update(int cur, int st, int ed, int x, int val) {
  if (st == ed) {
    seg[cur] = val;
    return;
  }
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  if (x <= mid)
    update(lft, st, mid, x, val);
  else
    update(rgt, mid + 1, ed, x, val);
  seg[cur] = (seg[lft] > seg[rgt] ? seg[rgt] : seg[lft]);
}
int main() {
  int i, j, k, lft, rgt;
  cin >> n >> s >> l;
  for (i = 1; i <= n; i++) {
    scanf("%d", &inp[i]);
  }
  insert1(1, 1, n);
  insert(1, 1, n);
  for (int i = (0); i < (n + 3); i++) dp[i] = INT_MAX / 3;
  dp[1] = 0;
  update(1, 1, n, 1, 0);
  for (i = 1; i <= n; i++) {
    L[i] = bs(i);
  }
  int low, high, mid, idx;
  for (i = 1; i <= n; i++) {
    rgt = i - l + 1, lft = L[i], idx = -1;
    while (lft <= rgt) {
      mid = (lft + rgt) / 2;
      pair<int, int> a = make_pair(INT_MAX / 3, -INT_MAX / 3);
      a = query1(1, 1, n, mid, i - l + 1);
      if (a.first - a.second <= s)
        idx = mid, rgt = mid - 1;
      else
        lft = mid + 1;
    }
    if (idx != -1 && (idx <= (i - l + 1))) {
      dp[i + 1] = (dp[i + 1] > answer(1, 1, n, idx, i - l + 1) + 1
                       ? answer(1, 1, n, idx, i - l + 1) + 1
                       : dp[i + 1]);
      update(1, 1, n, i + 1, dp[i + 1]);
    }
  }
  if (dp[n + 1] == INT_MAX / 3) dp[n + 1] = -1;
  cout << dp[n + 1] << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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.

Input

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

Output the minimal number of strip pieces.

If there are no ways to split the strip, output -1.

Examples

Input

7 2 2
1 3 1 2 4 1 2


Output

3


Input

7 2 2
1 100 1 100 1 100 1


Output

-1

Note

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline string toString(T a) {
  ostringstream os("");
  os << a;
  return os.str();
}
template <typename T>
inline long long toLong(T a) {
  long long res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline int toInt(T a) {
  int res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline double toDouble(T a) {
  double res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline T SQ(T a) {
  return a * a;
}
template <typename T>
inline T GCD(T a, T b) {
  if (b == 0)
    return a;
  else
    return GCD(b, a % b);
}
template <typename T>
inline T LCM(T a, T b) {
  long long res = a * b;
  res /= GCD(a, b);
  return res;
}
template <typename T>
inline unsigned long long BIGMOD(T a, T b, T m) {
  if (b == 0)
    return 1;
  else if (b % 2 == 0)
    return SQ(BIGMOD(a, b / 2, m)) % m;
  else
    return (a % m * BIGMOD(a, b - 1, m)) % m;
}
template <typename T>
inline vector<string> PARSE(T str) {
  vector<string> res;
  string s;
  istringstream os(str);
  while (os >> s) res.push_back(s);
  return res;
}
template <typename T>
inline unsigned long long DIST(T A, T B) {
  unsigned long long res =
      (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
  return res;
}
template <typename T>
inline long long CROSS(T A, T B, T C) {
  return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
template <typename T>
inline double cosAngle(T a, T b, T c) {
  double res = a * a + b * b - c * c;
  res = res / (2 * a * b);
  res = acos(res);
  return res;
}
template <typename T>
inline T POWER(T base, int po) {
  T res = 1;
  if (base == 0) return 0;
  for (int i = (0); i < (po); i++) res *= base;
  return res;
}
template <typename T>
inline bool IS_ON(T mask, T pos) {
  return mask & (1 << pos);
}
template <typename T>
inline int OFF(T mask, T pos) {
  return mask ^ (1 << pos);
}
template <typename T>
inline int ON(T mask, T pos) {
  return mask | (1 << pos);
}
template <typename T>
inline bool INSIDE_GRID(int R, int C, int ro, int clm) {
  if (R >= 0 && C >= 0 && R < ro && C < clm) return 1;
  return 0;
}
struct Z {
  int boro, choto;
  Z(){};
};
Z tree[4 * 100005];
int inp[100005];
int L[100005];
int seg[4 * 100005];
int dp[100005];
int n, l, s;
void insert1(int cur, int st, int ed) {
  if (st == ed) {
    tree[cur].choto = inp[st];
    tree[cur].boro = inp[st];
    return;
  }
  int mid, lft, rgt;
  mid = (st + ed) / 2;
  lft = 2 * cur, rgt = lft + 1;
  insert1(lft, st, mid);
  insert1(rgt, mid + 1, ed);
  tree[cur].choto =
      (tree[lft].choto > tree[rgt].choto ? tree[rgt].choto : tree[lft].choto);
  tree[cur].boro =
      (tree[lft].boro > tree[rgt].boro ? tree[lft].boro : tree[rgt].boro);
}
pair<int, int> query1(int cur, int st, int ed, int x, int y) {
  if (st == x && ed == y) {
    return make_pair(tree[cur].boro, tree[cur].choto);
  }
  int mid, lft, rgt;
  mid = (st + ed) / 2;
  lft = cur * 2, rgt = lft + 1;
  if (y <= mid)
    return query1(lft, st, mid, x, y);
  else if (x > mid)
    return query1(rgt, mid + 1, ed, x, y);
  else {
    pair<int, int> a = query1(lft, st, mid, x, mid);
    pair<int, int> b = query1(rgt, mid + 1, ed, mid + 1, y);
    a.first = max(a.first, b.first);
    a.second = min(a.second, b.second);
    return a;
  }
}
int bs(int x) {
  int best = x, low = 1, high = x, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    pair<int, int> a = query1(1, 1, n, mid, x);
    if (a.first - a.second <= s) {
      best = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  return best;
}
void insert(int cur, int st, int ed) {
  if (st == ed) {
    seg[cur] = INT_MAX / 3;
    return;
  }
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  insert(lft, st, mid);
  insert(rgt, mid + 1, ed);
  seg[cur] = (seg[lft] > seg[rgt] ? seg[rgt] : seg[lft]);
}
int answer(int cur, int st, int ed, int x, int y) {
  if (st == x && ed == y) return seg[cur];
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  if (y <= mid)
    return answer(lft, st, mid, x, y);
  else if (x > mid)
    return answer(rgt, mid + 1, ed, x, y);
  else
    return (answer(lft, st, mid, x, mid) > answer(rgt, mid + 1, ed, mid + 1, y)
                ? answer(rgt, mid + 1, ed, mid + 1, y)
                : answer(lft, st, mid, x, mid));
}
void update(int cur, int st, int ed, int x, int val) {
  if (st == ed) {
    seg[cur] = val;
    return;
  }
  int mid = (st + ed) / 2, lft = 2 * cur, rgt = lft + 1;
  if (x <= mid)
    update(lft, st, mid, x, val);
  else
    update(rgt, mid + 1, ed, x, val);
  seg[cur] = (seg[lft] > seg[rgt] ? seg[rgt] : seg[lft]);
}
int main() {
  int i, j, k, lft, rgt;
  cin >> n >> s >> l;
  for (i = 1; i <= n; i++) {
    scanf("%d", &inp[i]);
  }
  insert1(1, 1, n);
  insert(1, 1, n);
  for (int i = (0); i < (n + 3); i++) dp[i] = INT_MAX / 3;
  dp[1] = 0;
  update(1, 1, n, 1, 0);
  for (i = 1; i <= n; i++) {
    L[i] = bs(i);
  }
  int low, high, mid, idx;
  for (i = 1; i <= n; i++) {
    rgt = i - l + 1, lft = L[i], idx = -1;
    while (lft <= rgt) {
      mid = (lft + rgt) / 2;
      pair<int, int> a = make_pair(INT_MAX / 3, -INT_MAX / 3);
      a = query1(1, 1, n, mid, i - l + 1);
      if (a.first - a.second <= s)
        idx = mid, rgt = mid - 1;
      else
        lft = mid + 1;
    }
    if (idx != -1 && (idx <= (i - l + 1))) {
      dp[i + 1] = (dp[i + 1] > answer(1, 1, n, idx, i - l + 1) + 1
                       ? answer(1, 1, n, idx, i - l + 1) + 1
                       : dp[i + 1]);
      update(1, 1, n, i + 1, dp[i + 1]);
    }
  }
  if (dp[n + 1] == INT_MAX / 3) dp[n + 1] = -1;
  cout << dp[n + 1] << endl;
  return 0;
}

```