#include <bits/stdc++.h>
using namespace std;
long long const dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
long long const dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
long long const LIM = 1e5 + 100;
long long const INF = 1e14, MOD = 1e9 + 7;
double const PI = 3.141592653589793, EPS = 1e-7;
long long n, ll, s, to[LIM], from[LIM];
vector<long long> a;
template <typename cmp_t>
struct sparse_table_t {
  static size_t const MAX_POWER = 32;
  vector<vector<long long>> table;
  vector<long long> log;
  cmp_t _cmp;
  long long cmp(long long x, long long y) { return _cmp(x, y) ? x : y; }
  sparse_table_t(vector<long long> const &a)
      : table(a.size(), vector<long long>(MAX_POWER, 0)), log(a.size() + 1, 0) {
    for (size_t i = 0; i < a.size(); ++i) {
      table[i][0] = a[i];
    }
    for (size_t power = 1; power < MAX_POWER; ++power) {
      for (size_t i = 0; i < a.size(); ++i) {
        size_t j = i + (1 << (power - 1));
        if (j < a.size()) {
          table[i][power] = cmp(table[i][power - 1], table[j][power - 1]);
        }
      }
    }
    for (size_t i = 1; i <= a.size(); ++i) {
      size_t j = 0;
      while ((1 << j) <= i) ++j;
      log[i] = j - 1;
    }
  }
  long long get(long long l, long long r) {
    return cmp(table[l][log[r - l]], table[r - (1 << log[r - l])][log[r - l]]);
  }
};
struct segment_tree_t {
  long long n;
  vector<long long> tree;
  segment_tree_t(long long n) : n(n), tree(4 * n) {
    fill(tree.begin(), tree.end(), INF);
  }
  long long get(long long u, long long tl, long long tr, long long l,
                long long r) {
    if (tl == l && tr == r) {
      return tree[u];
    } else {
      long long tm = (tl + tr) / 2;
      if (r <= tm) {
        return get(2 * u, tl, tm, l, r);
      } else if (l >= tm) {
        return get(2 * u + 1, tm, tr, l, r);
      } else {
        long long a = get(2 * u, tl, tm, l, tm);
        long long b = get(2 * u + 1, tm, tr, tm, r);
        return min(a, b);
      }
    }
  }
  void insert(long long u, long long tl, long long tr, long long pos,
              long long x) {
    if (tr - tl == 1) {
      tree[u] = min(tree[u], x);
    } else {
      long long tm = (tl + tr) / 2;
      if (pos < tm) {
        insert(2 * u, tl, tm, pos, x);
      } else {
        insert(2 * u + 1, tm, tr, pos, x);
      }
      tree[u] = min(tree[2 * u], tree[2 * u + 1]);
    }
  }
  void insert(long long pos, long long x) { insert(1, 0, n, pos, x); }
  long long get(long long l, long long r) {
    if (r <= l) return INF;
    return get(1, 0, n, l, r);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> s >> ll;
  a.resize(n);
  for (long long i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sparse_table_t<less<long long>> ls(a);
  sparse_table_t<greater<long long>> gt(a);
  segment_tree_t segment_tree(n);
  for (long long i = n - 1; i >= 0; --i) {
    long long l = -1, r = i;
    while (r - l > 1) {
      long long m = (l + r) / 2;
      if (gt.get(m, i + 1) - ls.get(m, i + 1) <= s) {
        r = m;
      } else {
        l = m;
      }
    }
    from[i] = r - 1;
    to[i] = i - ll;
  }
  for (long long i = 0; i < n; ++i) {
    if (to[i] < from[i]) {
      continue;
    }
    if (from[i] < 0) {
      segment_tree.insert(i, 1);
    } else {
      long long val = segment_tree.get(from[i], to[i] + 1);
      if (val != INF) {
        segment_tree.insert(i, val + 1);
      }
    }
  }
  long long answer = segment_tree.get(n - 1, n);
  if (answer == INF) {
    cout << -1 << '\n';
  } else {
    cout << answer << '\n';
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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;
long long const dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
long long const dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
long long const LIM = 1e5 + 100;
long long const INF = 1e14, MOD = 1e9 + 7;
double const PI = 3.141592653589793, EPS = 1e-7;
long long n, ll, s, to[LIM], from[LIM];
vector<long long> a;
template <typename cmp_t>
struct sparse_table_t {
  static size_t const MAX_POWER = 32;
  vector<vector<long long>> table;
  vector<long long> log;
  cmp_t _cmp;
  long long cmp(long long x, long long y) { return _cmp(x, y) ? x : y; }
  sparse_table_t(vector<long long> const &a)
      : table(a.size(), vector<long long>(MAX_POWER, 0)), log(a.size() + 1, 0) {
    for (size_t i = 0; i < a.size(); ++i) {
      table[i][0] = a[i];
    }
    for (size_t power = 1; power < MAX_POWER; ++power) {
      for (size_t i = 0; i < a.size(); ++i) {
        size_t j = i + (1 << (power - 1));
        if (j < a.size()) {
          table[i][power] = cmp(table[i][power - 1], table[j][power - 1]);
        }
      }
    }
    for (size_t i = 1; i <= a.size(); ++i) {
      size_t j = 0;
      while ((1 << j) <= i) ++j;
      log[i] = j - 1;
    }
  }
  long long get(long long l, long long r) {
    return cmp(table[l][log[r - l]], table[r - (1 << log[r - l])][log[r - l]]);
  }
};
struct segment_tree_t {
  long long n;
  vector<long long> tree;
  segment_tree_t(long long n) : n(n), tree(4 * n) {
    fill(tree.begin(), tree.end(), INF);
  }
  long long get(long long u, long long tl, long long tr, long long l,
                long long r) {
    if (tl == l && tr == r) {
      return tree[u];
    } else {
      long long tm = (tl + tr) / 2;
      if (r <= tm) {
        return get(2 * u, tl, tm, l, r);
      } else if (l >= tm) {
        return get(2 * u + 1, tm, tr, l, r);
      } else {
        long long a = get(2 * u, tl, tm, l, tm);
        long long b = get(2 * u + 1, tm, tr, tm, r);
        return min(a, b);
      }
    }
  }
  void insert(long long u, long long tl, long long tr, long long pos,
              long long x) {
    if (tr - tl == 1) {
      tree[u] = min(tree[u], x);
    } else {
      long long tm = (tl + tr) / 2;
      if (pos < tm) {
        insert(2 * u, tl, tm, pos, x);
      } else {
        insert(2 * u + 1, tm, tr, pos, x);
      }
      tree[u] = min(tree[2 * u], tree[2 * u + 1]);
    }
  }
  void insert(long long pos, long long x) { insert(1, 0, n, pos, x); }
  long long get(long long l, long long r) {
    if (r <= l) return INF;
    return get(1, 0, n, l, r);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> s >> ll;
  a.resize(n);
  for (long long i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sparse_table_t<less<long long>> ls(a);
  sparse_table_t<greater<long long>> gt(a);
  segment_tree_t segment_tree(n);
  for (long long i = n - 1; i >= 0; --i) {
    long long l = -1, r = i;
    while (r - l > 1) {
      long long m = (l + r) / 2;
      if (gt.get(m, i + 1) - ls.get(m, i + 1) <= s) {
        r = m;
      } else {
        l = m;
      }
    }
    from[i] = r - 1;
    to[i] = i - ll;
  }
  for (long long i = 0; i < n; ++i) {
    if (to[i] < from[i]) {
      continue;
    }
    if (from[i] < 0) {
      segment_tree.insert(i, 1);
    } else {
      long long val = segment_tree.get(from[i], to[i] + 1);
      if (val != INF) {
        segment_tree.insert(i, val + 1);
      }
    }
  }
  long long answer = segment_tree.get(n - 1, n);
  if (answer == INF) {
    cout << -1 << '\n';
  } else {
    cout << answer << '\n';
  }
  return 0;
}

```