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.*;
import java.util.*;
public final class strip
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static int[][] st,st2;
	static int[] log,a,first;
	static long[] dp;
	static int maxn=100004;
	static long[] tree;
	
	static int rmq1(int l,int r)
	{
		int val=log[r-l];
		int x=st[val][l],y=st[val][r-(1<<val)+1];
		return Math.min(a[x],a[y]);
	}
	
	static int rmq2(int l,int r)
	{
		int val=log[r-l];
		int x=st2[val][l],y=st2[val][r-(1<<val)+1];
		return Math.max(a[x],a[y]);
	}
	
	static void update(int node,int s,int e,int l,int r,long val)
	{
		if(s>e || l>e || r<s)
		{
			return;
		}
		if(s==e)
		{
			tree[node]=val;
		}
		else
		{
			int mid=(s+e)>>1;
			update(node<<1,s,mid,l,r,val);update(node<<1|1,mid+1,e,l,r,val);
			tree[node]=Math.min(tree[node<<1],tree[node<<1|1]);
		}
	}
	
	static long get(int node,int s,int e,int l,int r)
	{
		if(s>e || l>e || r<s)
		{
			return Integer.MAX_VALUE;
		}
		if(l<=s && r>=e)
		{
			return tree[node];
		}
		else
		{
			int mid=(s+e)>>1;
			long q1=get(node<<1,s,mid,l,r),q2=get(node<<1|1,mid+1,e,l,r);
			return Math.min(q1,q2);
		}
	}
	
	public static void main(String args[]) throws Exception
	{
		int n=sc.nextInt(),s=sc.nextInt(),l=sc.nextInt();a=new int[n];log=new int[maxn];first=new int[n];dp=new long[n];tree=new long[4*n];
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
		}
		for(int i=2;i<maxn;i++)
		{
			log[i]=log[i>>1]+1;
		}
		st=new int[log[n]+1][n];st2=new int[log[n]+1][n];
		for(int i=0;i<n;i++)
		{
			st[0][i]=i;
			st2[0][i]=i;
		}
		for(int mask=1;(1<<mask)<=n;mask++)
		{
			for(int i=0;i+(1<<mask)<=n;i++)
			{
				int x=st[mask-1][i],y=st[mask-1][i+(1<<(mask-1))];
				st[mask][i]=(a[x]<=a[y])?x:y;
				int x1=st2[mask-1][i],y1=st2[mask-1][i+(1<<(mask-1))];
				st2[mask][i]=(a[x1]>=a[y1])?x1:y1;
			}
		}
		for(int i=0;i<n;i++)
		{
			int low=0,high=i;
			while(low<high)
			{
				int mid=(low+high+1)>>1,val1=rmq1(i-mid,i),val2=rmq2(i-mid,i);
				if(Math.abs(a[i]-val1)<=s && Math.abs(a[i]-val2)<=s)
				{
					low=mid;
				}
				else
				{
					high=mid-1;
				}
			}
			first[i]=i-low;
		}
		int max=-1;
		for(int i=0;i<n;i++)
		{
			max=Math.max(max,first[i]);
			first[i]=max;
		}
		for(int i=0;i<n;i++)
		{
			if(i<l-1 || i-first[i]+1<l)
			{
				dp[i]=Integer.MAX_VALUE;
			}
			else if(first[i]==0)
			{
				dp[i]=1;
			}
			else
			{
				long val=get(1,0,n-1,first[i]-1,i-l)+1;
				dp[i]=val;
			}
			update(1,0,n-1,i,i,dp[i]);
		}
		//out.println(Arrays.toString(first)+"\n"+Arrays.toString(dp));
		out.println(dp[n-1]<=n?dp[n-1]:-1);
		out.close();
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}