There are several days left before the fiftieth birthday of a famous Berland's writer Berlbury. In this connection the local library decided to make an exposition of the works of this famous science-fiction writer. It was decided as well that it is necessary to include into the exposition only those books that were published during a particular time period. It is obvious that if the books differ much in size, the visitors will not like it. That was why the organizers came to the opinion, that the difference between the highest and the lowest books in the exposition should be not more than k millimeters.

The library has n volumes of books by Berlbury, arranged in chronological order of their appearance. The height of each book in millimeters is know, it is hi. As Berlbury is highly respected in the city, the organizers want to include into the exposition as many books as possible, and to find out what periods of his creative work they will manage to cover. You are asked to help the organizers cope with this hard task.

Input

The first line of the input data contains two integer numbers separated by a space n (1 ≤ n ≤ 105) and k (0 ≤ k ≤ 106) — the amount of books by Berlbury in the library, and the maximum allowed height difference between the lowest and the highest books. The second line contains n integer numbers separated by a space. Each number hi (1 ≤ hi ≤ 106) is the height of the i-th book in millimeters.

Output

In the first line of the output data print two numbers a and b (separate them by a space), where a is the maximum amount of books the organizers can include into the exposition, and b — the amount of the time periods, during which Berlbury published a books, and the height difference between the lowest and the highest among these books is not more than k milllimeters.

In each of the following b lines print two integer numbers separated by a space — indexes of the first and the last volumes from each of the required time periods of Berlbury's creative work.

Examples

Input

3 3
14 12 10


Output

2 2
1 2
2 3


Input

2 0
10 10


Output

2 1
1 2


Input

4 5
8 19 10 13


Output

2 1
3 4
import java.io.*;
import java.math.*;
import java.security.KeyStore.Entry;
import java.util.*;


public class Main {
	private InputStream is;
	private PrintWriter out;
	int time = 0, start[], red[], black[], MOD = (int)(1e9+7), arr[];
	ArrayList<Integer>[] amp;
	boolean b[];
	Pair prr[];
	void solve() {
		int n = ni(), k = ni();
		int arr[] = na(n);
		int brr[] = new int[n];
		for(int i = 0; i< n;i++) brr[i] = -arr[i];
		ST1 st1 = new ST1(arr);
		ST1 st2 = new ST1(brr);
		int ans = 0, temp = 0, cnt = 0;
		int aa[] = new int[n];
		for(int i = 0; i< n ;i++){
			int low = i, high = n-1;
			int a = i;
			while(low<=high){
				int mid = (low+high)>>1;
				int a1 = st1.get(0, n-1, i, mid, 1), a2 = -st2.get(0, n-1, i, mid, 1);
				if(a2-a1<=k){
					a = mid;
					low = mid+1;
				}
				else{
					high = mid-1;
				}
			}
			if((a-i+1)>ans){
				cnt = 1;
				ans = a-i+1;
			}
			else if((a-i+1)==ans){
				cnt++;
			}
			aa[i] = (a-i+1);
		}
		System.out.println(ans+" "+cnt);
		for(int i = 0; i< n ;i++){
			if(aa[i]==ans){
				System.out.println((i+1)+" "+(ans+i));
			}
		}
	}
	static class ST1{
		int arr[], st[], size;
		ST1(int a[]){
			arr = a.clone();
			size = 10*arr.length;
			st = new int[size];
			build(0,arr.length-1,1);
		}
		void build(int ss, int se, int si){
			if(ss==se){
				st[si] = arr[ss];
				return;
			}
			int mid = (ss+se)/2;
			int val = 2*si;
			build(ss,mid,val); build(mid+1,se,val+1);
			st[si] = Math.min(st[val], st[val+1]);
		}
		int get(int ss, int se, int l, int r, int si){
			if(l>se || r<ss || l>r) return Integer.MAX_VALUE;
			if(l<=ss && r>=se) return st[si];
			int mid = (ss+se)/2;
			int val = 2*si;
			return Math.min(get(ss,mid,l,r,val), get(mid+1,se,l,r,val+1));
		}
	}
	static class ST{
		int arr[],lazy[],n;
		ST(int a){
			n = a;
			arr = new int[10*n];
			lazy = new int[10*n];
		}
		void up(int l,int r,int val){
			update(0,n-1,0,l,r,val);
		}
		void update(int l,int r,int c,int x,int y,int val){
			if(lazy[c]!=0){
				lazy[2*c+1]+=lazy[c];
				lazy[2*c+2]+=lazy[c];
				if(l==r)
					arr[c]+=lazy[c];
				lazy[c] = 0;
			}
			if(l>r||x>y||l>y||x>r)
				return;
			if(x<=l&&y>=r){
				lazy[c]+=val;
				return ;
			}
			int mid = l+r>>1;
			update(l,mid,2*c+1,x,y,val);
			update(mid+1,r,2*c+2,x,y,val);
			arr[c] = Math.max(arr[2*c+1], arr[2*c+2]);
		}
		int an(int ind){
			return ans(0,n-1,0,ind);
		}
		int ans(int l,int r,int c,int ind){
			if(lazy[c]!=0){
				lazy[2*c+1]+=lazy[c];
				lazy[2*c+2]+=lazy[c];
				if(l==r)
					arr[c]+=lazy[c];
				lazy[c] = 0;
			}
			if(l==r)
				return arr[c];
			int mid = l+r>>1;
			if(mid>=ind)
				return ans(l,mid,2*c+1,ind);
			return ans(mid+1,r,2*c+2,ind);
		}
	}
	public static class FenwickTree {
		
	    int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates

	    public FenwickTree(int size) {
	        array = new int[size + 1];
	    }
	    public int rsq(int ind) {
	        assert ind > 0;
	        int sum = 0;
	        while (ind > 0) {
	            sum += array[ind];
	            //Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
	            ind -= ind & (-ind);
	        }
	        return sum;
	    }
	    public int rsq(int a, int b) {
	        assert b >= a && a > 0 && b > 0;
	        return rsq(b) - rsq(a - 1);
	    }
	    public void update(int ind, int value) {
	        assert ind > 0;
	        while (ind < array.length) {
	            array[ind] += value;
	            //Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
	            ind += ind & (-ind);
	        }
	    }
	    public int size() {
	        return array.length - 1;
	    }
	}
	int dfs1(int x){
		start[x] = time++;
		b[x] = true;
		if(arr[x]==0) red[x]++;
		for(int i : amp[x]){
			if(!b[i]){
				red[x] += dfs1(i);
			}
		}
		return red[x];
	}
	int dfs2(int x){
		if(arr[x]==1) black[x]++;
		b[x] = true;
		for(int i : amp[x]){
			if(!b[i]){
				black[x] += dfs2(i);
			}
		}
		return black[x];
	}
	void buildGraph(int n){
		for(int i = 0; i< n; i++){
			int x = ni()-1, y = ni() - 1,w = ni();
			prr[i] = new Pair(x,y,w);
			amp[x].add(y);
			amp[y].add(x);
		}
	}
	public static int[] shuffle(int[] a, Random gen){
		for(int i = 0, n = a.length;i < n;i++)
		{ 
			int ind = gen.nextInt(n-i)+i; 
			int d = a[i]; 
			a[i] = a[ind];
			a[ind] = d; 
		} 
	return a; 
	}

	class Pair implements Comparable<Pair>{
		int u, v, w;
		Pair(int u, int v, int w){
			this.u = u;
			this.v = v;
			this.w = w;
		}public int hashCode() {
			return Objects.hash();
		}
		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return ((u == other.u && v == other.v) || (v == other.u && u == other.v));
		}
		public int compareTo(Pair other) {
			//return Integer.compare(val, other.val);
			return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v,other.v));
		}
	}
	long power(long x, long y){
		long ans = 1;
		while(y>0){
			if(y%2==0){
				x = (x*x)%MOD;
				y/=2;
			}
			else{
				ans = (x*ans)%MOD;
				y--;
			}
		}
		return ans;
	}
	void soln() {
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		//out.close();
		out.flush();
		//tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new Main().soln();
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}