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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            BStrip solver = new BStrip();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class BStrip {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int s = in.ri();
            int l = in.ri();
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = in.ri();
            }
            a[0] = (long) 1e18;
            int inf = (int) 1e9;
            Segment st = new Segment(0, n, i -> i == 0 ? 0 : inf);
            LongMinQueue minQueue = new LongMinQueue(n + 1, LongComparator.NATURE_ORDER);
            LongMinQueue maxQueue = new LongMinQueue(n + 1, LongComparator.REVERSE_ORDER);
            for (int i = 1; i <= n; i++) {
                minQueue.addLast(a[i]);
                maxQueue.addLast(a[i]);
                while (!maxQueue.isEmpty() && maxQueue.min() - minQueue.min() > s) {
                    maxQueue.removeFirst();
                    minQueue.removeFirst();
                }
                int L = i - maxQueue.size();
                int R = i - l;
                int best = st.query(L, R, 0, n) + 1;
                st.update(i, i, 0, n, best);
            }
            int ans = st.query(n, n, 0, n);
            out.println(ans >= inf ? -1 : ans);
        }

    }

    static interface LongDeque extends LongStack {
    }

    static class LongMinQueue {
        LongDequeImpl minQueue;
        LongDequeImpl data;
        LongComparator comparator;

        public LongMinQueue(int cap, LongComparator comparator) {
            minQueue = new LongDequeImpl(cap);
            data = new LongDequeImpl(cap);
            this.comparator = comparator;
        }

        public void addLast(long val) {
            data.addLast(val);
            while (!minQueue.isEmpty() && comparator.compare(minQueue.peekLast(), val) > 0) {
                minQueue.removeLast();
            }
            minQueue.addLast(val);
        }

        public long removeFirst() {
            assert size() > 0;
            long val = data.removeFirst();
            if (minQueue.peekFirst() == val) {
                minQueue.removeFirst();
            }
            return val;
        }

        public int size() {
            return data.size();
        }

        public long min() {
            assert size() > 0;
            return minQueue.peekFirst();
        }

        public boolean isEmpty() {
            return data.isEmpty();
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static interface LongComparator {
        public static final LongComparator NATURE_ORDER = (a, b) -> Long.compare(a, b);
        public static final LongComparator REVERSE_ORDER = (a, b) -> Long.compare(b, a);

        public int compare(long a, long b);

    }

    static interface LongIterator {
        boolean hasNext();

        long next();

    }

    static class Segment implements Cloneable {
        static int inf = (int) 1e9;
        private Segment left;
        private Segment right;
        int min;

        private void modify(int x) {
            min = x;
        }

        public void pushUp() {
            min = Math.min(left.min, right.min);
        }

        public void pushDown() {
        }

        public Segment(int l, int r, IntToIntegerFunction func) {
            if (l < r) {
                int m = DigitUtils.floorAverage(l, r);
                left = new Segment(l, m, func);
                right = new Segment(m + 1, r, func);
                pushUp();
            } else {
                min = func.apply(l);
            }
        }

        private boolean enter(int L, int R, int l, int r) {
            return L <= l && R >= r;
        }

        private boolean leave(int L, int R, int l, int r) {
            return L > r || R < l;
        }

        public void update(int L, int R, int l, int r, int x) {
            if (leave(L, R, l, r)) {
                return;
            }
            if (enter(L, R, l, r)) {
                modify(x);
                return;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            left.update(L, R, l, m, x);
            right.update(L, R, m + 1, r, x);
            pushUp();
        }

        public int query(int L, int R, int l, int r) {
            if (leave(L, R, l, r)) {
                return inf;
            }
            if (enter(L, R, l, r)) {
                return min;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            return Math.min(left.query(L, R, l, m),
                    right.query(L, R, m + 1, r));
        }

        private Segment deepClone() {
            Segment seg = clone();
            if (seg.left != null) {
                seg.left = seg.left.deepClone();
            }
            if (seg.right != null) {
                seg.right = seg.right.deepClone();
            }
            return seg;
        }

        protected Segment clone() {
            try {
                return (Segment) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        private void toString(StringBuilder builder) {
            if (left == null && right == null) {
                builder.append("val").append(",");
                return;
            }
            pushDown();
            left.toString(builder);
            right.toString(builder);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            deepClone().toString(builder);
            if (builder.length() > 0) {
                builder.setLength(builder.length() - 1);
            }
            return builder.toString();
        }

    }

    static interface LongStack {
    }

    static interface IntToIntegerFunction {
        int apply(int x);

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class LongDequeImpl implements LongDeque {
        private long[] data;
        private int bpos;
        private int epos;
        private static final long[] EMPTY = new long[0];
        private int n;

        public LongDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new long[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            long[] newData = new long[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public LongIterator iterator() {
            return new LongIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public long next() {
                    long ans = data[index];
                    index = LongDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public long removeFirst() {
            long ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public long removeLast() {
            long ans = data[last(epos)];
            epos = last(epos);
            return ans;
        }

        public void addLast(long x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public long peekFirst() {
            return data[bpos];
        }

        public long peekLast() {
            return data[last(epos)];
        }

        private int last(int x) {
            return (x == 0 ? n : x) - 1;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public boolean isEmpty() {
            return bpos == epos;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (LongIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }
}

