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.util.*;

public class BOOKS { //these sites need to decide whether they actually like public classes
	public static BufferedReader buffstdin = new BufferedReader(new InputStreamReader(System.in));
	static OutputStream out = new BufferedOutputStream ( System.out );
	
	public static void Sprintln(Object s) throws IOException {
		String S = s + "";
		System.out.println(S);
	}
	public static void Sprint(Object s) throws IOException {
		System.out.print("" + s);
	}
	public static void println(Object s) throws IOException {
		String S = s + "\n";
		out.write(S.getBytes());
	}
	public static void println() throws IOException {
		out.write("\n".getBytes());
	}
	public static void print(Object s) throws IOException {
		out.write(("" + s).getBytes());
	}
	public static int Int(String s) {
		return Integer.parseInt(s);
	}
	public static String[] getLine() throws IOException {
		return buffstdin.readLine().trim().split(" ");
	}
	public static String getString() throws IOException {
		return buffstdin.readLine().trim();
	}
	public static int getInt() throws IOException {
		return Int(getString());
	}
	public static int[] getIntLine() throws IOException {
		String[] line = buffstdin.readLine().trim().split(" ");
		int[] a = new int[line.length];
		for(int i : range(line.length))	a[i] = Int(line[i]);
		return a;
	}
	public static int[] range(int u) {
		int[] array = new int[u];
		for(int i=0; i<u; i++) array[i] = i;
		return array;
	}
	public static int[] range(int l, int u) {
		int[] array = new int[u-l];
		for(int i=0; i<u-l; i++) array[i] = l+i;
		return array;
	}
	
	public static class range implements Comparable<range>{
		int l,r;
		public range(int L, int R) {
			l=L+1; r=R; //uses stupid 1-based indexing, except with r, just because why not
		}
		
		public int size() {
			return r-l;
		}
		
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(l);
			sb.append(" ");
			sb.append(r);
			return sb.toString();
		}
		
		@Override
		public int compareTo(range r) {
			return size() - r.size();
		}
	}
	
	public static int specialGet(SortedMap<Integer, Integer> tree, int index) {
		int value=0;
		if(tree.get(index) != null) {
			value=tree.get(index);
		}
		return 1+value;
	}
	
	public static String solve(int n, int k, int[] books) throws IOException {
		StringBuilder sb = new StringBuilder("");
		//for(int b : books) //Sprintln(b);
		ArrayList<range> maxRanges = new ArrayList<range>(); //keeps track of ranges
		int maxSize=0; //keeps track of the maximum range size
		int l=0,r=0;
		int delta;
		SortedMap<Integer,Integer> tree = new TreeMap<>(); //keeps track of the height, and the number of books with that height
		while(r<n) { //when r reaches n, you'll get issues, so don't to that. 
			tree.put(books[r], specialGet(tree, books[r])); // if doesn't exist, add it, else increment counter
			r++; //conditions sorted out in while condition
			delta = tree.lastKey() - tree.firstKey();
			while(delta > k) { //while invalid (can't just remove, since we keep a "count" value)
				//Sprintln((delta) + "\t" + k);
				//Sprintln(l + " " + r);
				//Sprintln("LastKey: " + tree.lastKey());
				//Sprintln("FirstKey: " + tree.firstKey());
				if(l >= r) {
					//Sprintln("l is larger than r... you might want to check on that");
					//Sprintln("LastKey: " + tree.lastKey());
					//Sprintln("FirstKey: " + tree.firstKey());
				}
				int count = tree.get(books[l]);
				if(count==1) { //if there's only one, just kill it. 
					tree.remove(books[l]);
				}
				else { //otherwise, you can just decrement and move on with your life
					tree.put(books[l], count-1);
				}
				if(count<1) {
					//Sprintln("Um so count is less than 1. Explain yourself.");
				}
				l++; //put it all behind you.
				delta = tree.lastKey()-tree.firstKey();
				//Sprintln((delta) + "\t" + k);
			}
			//now it's valid (as far as you know), so you can get to this stuff
			if(r-l == maxSize) { //check against max Size
				maxRanges.add(new range(l,r));//if equal, add range to maxRanges
			}
			else if(r-l > maxSize) {
				maxRanges.clear();//if larger, dump maxRanges and add to maxRanges
				maxRanges.add(new range(l,r));
				maxSize=r-l;
			}
			//if it's smaller than maxSize, it doesn't matter to us, just keep going
		}
		sb.append(maxSize);
		sb.append(" ");
		sb.append(maxRanges.size());
		sb.append("\n");
		for(range ra : maxRanges) {
			sb.append(ra);
			sb.append("\n");
		}
		return sb.toString();
	}
	
	public static void main(String[] args) throws IOException {
		int[] line = getIntLine();
		int n=line[0];
		int k = line[1];
		int[] books = getIntLine();
		println(solve(n, k, books));			
		
		out.flush();
	}
}
