#include <bits/stdc++.h>
using namespace std;
template <typename T, typename T1>
ostream &operator<<(ostream &out, pair<T, T1> obj) {
  out << "(" << obj.first << "," << obj.second << ")";
  return out;
}
template <typename T, typename T1>
ostream &operator<<(ostream &out, map<T, T1> cont) {
  typename map<T, T1>::const_iterator itr = cont.begin();
  typename map<T, T1>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, set<T> cont) {
  typename set<T>::const_iterator itr = cont.begin();
  typename set<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, multiset<T> cont) {
  typename multiset<T>::const_iterator itr = cont.begin();
  typename multiset<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T,
          template <typename ELEM, typename ALLOC = allocator<ELEM>> class CONT>
ostream &operator<<(ostream &out, CONT<T> cont) {
  typename CONT<T>::const_iterator itr = cont.begin();
  typename CONT<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T, unsigned int N, typename CTy, typename CTr>
typename enable_if<!is_same<T, char>::value, basic_ostream<CTy, CTr> &>::type
operator<<(basic_ostream<CTy, CTr> &out, const T (&arr)[N]) {
  for (auto i = 0; i < N; ++i) out << arr[i] << " ";
  out << endl;
  return out;
}
template <typename T>
T gcd(T a, T b) {
  T min_v = min(a, b);
  T max_v = max(a, b);
  while (min_v) {
    T temp = max_v % min_v;
    max_v = min_v;
    min_v = temp;
  }
  return max_v;
}
template <typename T>
T lcm(T a, T b) {
  return (a * b) / gcd(a, b);
}
template <typename T>
T fast_exp_pow(T base, T exp, T mod) {
  long long res = 1;
  while (exp) {
    if (exp & 1) {
      res *= base;
      res %= mod;
    }
    exp >>= 1;
    base *= base;
    base %= mod;
  }
  return res % mod;
}
int N, L, Tbeg, Tend, Tmid;
long long S;
long long numbers[100010], dp_solve[100010], seg_tree_1[100010];
pair<long long, long long> seg_tree[4 * 100010];
void build(int Tbeg = 0, int Tend = N - 1, int ind = 0) {
  if (Tbeg == Tend) {
    seg_tree[ind] = make_pair(numbers[Tbeg], numbers[Tbeg]);
    return;
  }
  int Tmid = (Tbeg + Tend) >> 1;
  build(Tbeg, Tmid, 2 * ind + 1);
  build(Tmid + 1, Tend, 2 * ind + 2);
  seg_tree[ind].first =
      min(seg_tree[2 * ind + 1].first, seg_tree[2 * ind + 2].first);
  seg_tree[ind].second =
      max(seg_tree[2 * ind + 1].second, seg_tree[2 * ind + 2].second);
}
pair<long long, long long> query(int Qbeg, int Qend, int Tbeg = 0,
                                 int Tend = N - 1, int ind = 0) {
  if (Tbeg >= Qbeg && Tend <= Qend) return seg_tree[ind];
  if (Tbeg > Qend || Tend < Qbeg) return make_pair(INT_MAX, -INT_MAX);
  int Tmid = (Tbeg + Tend) >> 1;
  pair<long long, long long> ret1 = query(Qbeg, Qend, Tbeg, Tmid, 2 * ind + 1);
  pair<long long, long long> ret2 =
      query(Qbeg, Qend, Tmid + 1, Tend, 2 * ind + 2);
  pair<long long, long long> ret =
      make_pair(min(ret1.first, ret2.first), max(ret1.second, ret2.second));
  return ret;
}
void update_1(int pos, long long value, int Tbeg = 0, int Tend = N,
              int ind = 0) {
  if (Tbeg == Tend && Tbeg == pos) {
    seg_tree_1[ind] = value;
    return;
  }
  if (Tbeg > pos || Tend < pos) return;
  int Tmid = (Tbeg + Tend) >> 1;
  update_1(pos, value, Tbeg, Tmid, 2 * ind + 1);
  update_1(pos, value, Tmid + 1, Tend, 2 * ind + 2);
  if (seg_tree_1[2 * ind + 1] == -1)
    seg_tree_1[ind] = seg_tree_1[2 * ind + 2];
  else if (seg_tree_1[2 * ind + 2] == -1)
    seg_tree_1[ind] = seg_tree_1[2 * ind + 1];
  else
    seg_tree_1[ind] = min(seg_tree_1[2 * ind + 1], seg_tree_1[2 * ind + 2]);
}
long long query_1(int Qbeg, int Qend, int Tbeg = 0, int Tend = N, int ind = 0) {
  if (Tbeg >= Qbeg && Tend <= Qend) return seg_tree_1[ind];
  if (Tbeg > Qend || Tend < Qbeg) return -1;
  int Tmid = (Tbeg + Tend) >> 1;
  long long ret1 = query_1(Qbeg, Qend, Tbeg, Tmid, 2 * ind + 1);
  long long ret2 = query_1(Qbeg, Qend, Tmid + 1, Tend, 2 * ind + 2);
  long long ret;
  if (ret1 == -1)
    ret = ret2;
  else if (ret2 == -1)
    ret = ret1;
  else
    ret = min(ret1, ret2);
  return ret;
}
int main() {
  scanf("%d%lld%d", &N, &S, &L);
  for (auto i = 0; i < N; ++i) scanf("%lld", numbers + i);
  build();
  memset(dp_solve, -1, sizeof(dp_solve));
  memset(seg_tree_1, -1, sizeof(seg_tree_1));
  update_1(0, 0);
  for (auto i = 1; i <= N; ++i) {
    Tbeg = 1, Tend = i;
    while (Tbeg < Tend) {
      Tmid = (Tbeg + Tend) >> 1;
      pair<long long, long long> ret = query(Tmid - 1, i - 1);
      if (ret.second - ret.first <= S)
        Tend = Tmid;
      else
        Tbeg = Tmid + 1;
    }
    if (i - Tend + 1 < L)
      dp_solve[i] = -1;
    else {
      if (i == 1) {
        if (L == 1) dp_solve[i] = 1;
      } else {
        long long ret = query_1(Tend - 1, i - L);
        if (ret != -1) dp_solve[i] = ret + 1;
      }
      update_1(i, dp_solve[i]);
    }
  }
  printf("%lld\n", dp_solve[N]);
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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, typename T1>
ostream &operator<<(ostream &out, pair<T, T1> obj) {
  out << "(" << obj.first << "," << obj.second << ")";
  return out;
}
template <typename T, typename T1>
ostream &operator<<(ostream &out, map<T, T1> cont) {
  typename map<T, T1>::const_iterator itr = cont.begin();
  typename map<T, T1>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, set<T> cont) {
  typename set<T>::const_iterator itr = cont.begin();
  typename set<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, multiset<T> cont) {
  typename multiset<T>::const_iterator itr = cont.begin();
  typename multiset<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T,
          template <typename ELEM, typename ALLOC = allocator<ELEM>> class CONT>
ostream &operator<<(ostream &out, CONT<T> cont) {
  typename CONT<T>::const_iterator itr = cont.begin();
  typename CONT<T>::const_iterator ends = cont.end();
  for (; itr != ends; ++itr) out << *itr << " ";
  out << endl;
  return out;
}
template <typename T, unsigned int N, typename CTy, typename CTr>
typename enable_if<!is_same<T, char>::value, basic_ostream<CTy, CTr> &>::type
operator<<(basic_ostream<CTy, CTr> &out, const T (&arr)[N]) {
  for (auto i = 0; i < N; ++i) out << arr[i] << " ";
  out << endl;
  return out;
}
template <typename T>
T gcd(T a, T b) {
  T min_v = min(a, b);
  T max_v = max(a, b);
  while (min_v) {
    T temp = max_v % min_v;
    max_v = min_v;
    min_v = temp;
  }
  return max_v;
}
template <typename T>
T lcm(T a, T b) {
  return (a * b) / gcd(a, b);
}
template <typename T>
T fast_exp_pow(T base, T exp, T mod) {
  long long res = 1;
  while (exp) {
    if (exp & 1) {
      res *= base;
      res %= mod;
    }
    exp >>= 1;
    base *= base;
    base %= mod;
  }
  return res % mod;
}
int N, L, Tbeg, Tend, Tmid;
long long S;
long long numbers[100010], dp_solve[100010], seg_tree_1[100010];
pair<long long, long long> seg_tree[4 * 100010];
void build(int Tbeg = 0, int Tend = N - 1, int ind = 0) {
  if (Tbeg == Tend) {
    seg_tree[ind] = make_pair(numbers[Tbeg], numbers[Tbeg]);
    return;
  }
  int Tmid = (Tbeg + Tend) >> 1;
  build(Tbeg, Tmid, 2 * ind + 1);
  build(Tmid + 1, Tend, 2 * ind + 2);
  seg_tree[ind].first =
      min(seg_tree[2 * ind + 1].first, seg_tree[2 * ind + 2].first);
  seg_tree[ind].second =
      max(seg_tree[2 * ind + 1].second, seg_tree[2 * ind + 2].second);
}
pair<long long, long long> query(int Qbeg, int Qend, int Tbeg = 0,
                                 int Tend = N - 1, int ind = 0) {
  if (Tbeg >= Qbeg && Tend <= Qend) return seg_tree[ind];
  if (Tbeg > Qend || Tend < Qbeg) return make_pair(INT_MAX, -INT_MAX);
  int Tmid = (Tbeg + Tend) >> 1;
  pair<long long, long long> ret1 = query(Qbeg, Qend, Tbeg, Tmid, 2 * ind + 1);
  pair<long long, long long> ret2 =
      query(Qbeg, Qend, Tmid + 1, Tend, 2 * ind + 2);
  pair<long long, long long> ret =
      make_pair(min(ret1.first, ret2.first), max(ret1.second, ret2.second));
  return ret;
}
void update_1(int pos, long long value, int Tbeg = 0, int Tend = N,
              int ind = 0) {
  if (Tbeg == Tend && Tbeg == pos) {
    seg_tree_1[ind] = value;
    return;
  }
  if (Tbeg > pos || Tend < pos) return;
  int Tmid = (Tbeg + Tend) >> 1;
  update_1(pos, value, Tbeg, Tmid, 2 * ind + 1);
  update_1(pos, value, Tmid + 1, Tend, 2 * ind + 2);
  if (seg_tree_1[2 * ind + 1] == -1)
    seg_tree_1[ind] = seg_tree_1[2 * ind + 2];
  else if (seg_tree_1[2 * ind + 2] == -1)
    seg_tree_1[ind] = seg_tree_1[2 * ind + 1];
  else
    seg_tree_1[ind] = min(seg_tree_1[2 * ind + 1], seg_tree_1[2 * ind + 2]);
}
long long query_1(int Qbeg, int Qend, int Tbeg = 0, int Tend = N, int ind = 0) {
  if (Tbeg >= Qbeg && Tend <= Qend) return seg_tree_1[ind];
  if (Tbeg > Qend || Tend < Qbeg) return -1;
  int Tmid = (Tbeg + Tend) >> 1;
  long long ret1 = query_1(Qbeg, Qend, Tbeg, Tmid, 2 * ind + 1);
  long long ret2 = query_1(Qbeg, Qend, Tmid + 1, Tend, 2 * ind + 2);
  long long ret;
  if (ret1 == -1)
    ret = ret2;
  else if (ret2 == -1)
    ret = ret1;
  else
    ret = min(ret1, ret2);
  return ret;
}
int main() {
  scanf("%d%lld%d", &N, &S, &L);
  for (auto i = 0; i < N; ++i) scanf("%lld", numbers + i);
  build();
  memset(dp_solve, -1, sizeof(dp_solve));
  memset(seg_tree_1, -1, sizeof(seg_tree_1));
  update_1(0, 0);
  for (auto i = 1; i <= N; ++i) {
    Tbeg = 1, Tend = i;
    while (Tbeg < Tend) {
      Tmid = (Tbeg + Tend) >> 1;
      pair<long long, long long> ret = query(Tmid - 1, i - 1);
      if (ret.second - ret.first <= S)
        Tend = Tmid;
      else
        Tbeg = Tmid + 1;
    }
    if (i - Tend + 1 < L)
      dp_solve[i] = -1;
    else {
      if (i == 1) {
        if (L == 1) dp_solve[i] = 1;
      } else {
        long long ret = query_1(Tend - 1, i - L);
        if (ret != -1) dp_solve[i] = ret + 1;
      }
      update_1(i, dp_solve[i]);
    }
  }
  printf("%lld\n", dp_solve[N]);
  return 0;
}

```