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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					long prevTime = System.currentTimeMillis();
					new Main().run();
					System.err.println("Total time: "
							+ (System.currentTimeMillis() - prevTime) + " ms");
					System.err.println("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start();
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		Object o = solve();
		if (o != null)
			out.println(o);
		out.close();
		in.close();
	}

	private Object solve() throws IOException {
		int n = ni();
		int s = ni();
		int l = ni();
		int[] arr = nia(n);
		RMQ_min min= new RMQ_min(arr);
		RMQ_max max= new RMQ_max(arr);
		int[] len = new int[n];
		
		int end = 1;
		for(int start =0; start<n;start++){
			while(end <= n && max.query(start, end) - min.query(start, end) <= s)
				end++;
			len[start] = end - start - 1;
		}
		
		int[] aux = new int[n];
		Arrays.fill(aux, Integer.MAX_VALUE);
		SegmentTree dp = new SegmentTree(aux);		// i -esimo me dice la minima cantidad de tiras, empezando desde i

		for(int i = n-1;i >=0;i--){
			if(len[i] < l)
				continue;
			
			if(i + len[i] >= n){
				dp.modify(i, 1);
				continue;
			}
			int query_result = dp.query(i + l , i + len[i] + 1);
			if(query_result != Integer.MAX_VALUE)
				dp.modify(i, query_result + 1);
			
		}
		int res = dp.query(0, 1);
		return (res==Integer.MAX_VALUE? -1 : res);
	}
	
	
	public class SegmentTree {
		
		int n;  // array size
		int[] t;
		
		public SegmentTree(int[] arr) {
			n = arr.length;
			t = new int[2*n];
			System.arraycopy(arr, 0, t, n, n);
			build();
		}

		void build() {  
		  for (int i = n - 1; i > 0; --i) t[i] = Math.min(t[i<<1] , t[i<<1|1]);
		}

		void modify(int p, int value) {  
		  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = Math.min(t[p] , t[p^1]);
		}

		int query(int l, int r) {  
		  int res_left = Integer.MAX_VALUE;													
		  int res_right = Integer.MAX_VALUE;
		  
		  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		    if ((l&1) != 0) res_left = Math.min(res_left , t[l++]);					
		    if ((r&1) != 0) res_right = Math.min(t[--r] , res_right);				
		  }
		  return Math.min(res_left , res_right);										
		}
	}
	class RMQ_min {
		int[] vs;
		int[][] min;		

		RMQ_min(int[] vs) {

			int n = vs.length, m = log2(n) + 1;
			this.vs = vs;

			min = new int[m][n];
			for (int i = 0; i < n; i++)
				min[0][i] = vs[i];				
			for (int i = 1, k = 1; i < m; i++, k <<= 1) {
				for (int j = 0; j + k < n; j++) {
					min[i][j] = min[i - 1][j] <= min[i - 1][j + k] ?  min[i - 1][j] : min[i - 1][j + k];
				}
			}
		}

		int query(int from, int to) {
			int k = log2(to - from);
			return min[k][from] <= min[k][to - (1 << k)] ? min[k][from] : min[k][to - (1 << k)];
		}

		int log2(int b) {
			return 31 - Integer.numberOfLeadingZeros(b);
		}
	}
	
	class RMQ_max {
		int[] vs;
		int[][] max;		

		RMQ_max(int[] vs) {

			int n = vs.length, m = log2(n) + 1;
			this.vs = vs;

			max = new int[m][n];
			for (int i = 0; i < n; i++)
				max[0][i] = vs[i];				
			for (int i = 1, k = 1; i < m; i++, k <<= 1) {
				for (int j = 0; j + k < n; j++) {
					max[i][j] = max[i - 1][j] >= max[i - 1][j + k] ?  max[i - 1][j] : max[i - 1][j + k];
				}
			}
		}

		int query(int from, int to) {
			int k = log2(to - from);
			return max[k][from] >= max[k][to - (1 << k)] ? max[k][from] : max[k][to - (1 << k)];
		}

		int log2(int b) {
			return 31 - Integer.numberOfLeadingZeros(b);
		}
	}


	BufferedReader in;
	PrintWriter out;
	StringTokenizer strTok = new StringTokenizer("");

	String nextToken() throws IOException {
		while (!strTok.hasMoreTokens())
			strTok = new StringTokenizer(in.readLine());
		return strTok.nextToken();
	}

	int ni() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nl() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nd() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int[] nia(int size) throws IOException {
		int[] ret = new int[size];
		for (int i = 0; i < size; i++)
			ret[i] = ni();
		return ret;
	}

	long[] nla(int size) throws IOException {
		long[] ret = new long[size];
		for (int i = 0; i < size; i++)
			ret[i] = nl();
		return ret;
	}

	double[] nda(int size) throws IOException {
		double[] ret = new double[size];
		for (int i = 0; i < size; i++)
			ret[i] = nd();
		return ret;
	}

	String nextLine() throws IOException {
		strTok = new StringTokenizer("");
		return in.readLine();
	}

	boolean EOF() throws IOException {
		while (!strTok.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			strTok = new StringTokenizer(s);
		}
		return false;
	}

	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}

	void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(long[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array, String spec) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}

	void printArray(Object[] array) {
		boolean blank = false;
		for (Object x : array) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		boolean blank = false;
		for (Object x : collection) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory()
				- Runtime.getRuntime().freeMemory() >> 20)
				+ "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}

	public void pln() {
		out.println();
	}

	public void pln(int arg) {
		out.println(arg);
	}

	public void pln(long arg) {
		out.println(arg);
	}

	public void pln(double arg) {
		out.println(arg);
	}

	public void pln(String arg) {
		out.println(arg);
	}

	public void pln(boolean arg) {
		out.println(arg);
	}

	public void pln(char arg) {
		out.println(arg);
	}

	public void pln(float arg) {
		out.println(arg);
	}

	public void pln(Object arg) {
		out.println(arg);
	}

	public void p(int arg) {
		out.print(arg);
	}

	public void p(long arg) {
		out.print(arg);
	}

	public void p(double arg) {
		out.print(arg);
	}

	public void p(String arg) {
		out.print(arg);
	}

	public void p(boolean arg) {
		out.print(arg);
	}

	public void p(char arg) {
		out.print(arg);
	}

	public void p(float arg) {
		out.print(arg);
	}

	public void p(Object arg) {
		out.print(arg);
	}

}