Mảng và giá trị tuyệt đối

Xem PDF

Điểm: 500 Thời gian: 0.5s Bộ nhớ: 162M Input: bàn phím Output: màn hình

Cho mảng \(A\) gồm \(n\) phần tử: \(A_1,A_2,...,A_n\) và một số nguyên dương \(k\).

Yêu cầu: Hãy tìm tất cả các cặp \((i,j)\) khác nhau thoả mãn các điều kiện sau:

  • \(1\le i\le j\le n\)

  • Gọi \(S\) là giá trị tuyệt đối giữa phần tử lớn nhất và phần tử nhỏ nhất của dãy: \(A_{i},A_{i+1},...,A_{j}\) thì \(S\le k\)

  • \(j-i+1\) lớn nhất có thể

Chú ý: Hai cặp \((u_1,v_1)\)\((u_2,v_2)\) được xem là khác nhau nếu \(u_1\ne u_2\) hoặc \(v_1\ne v_2\).

Input

  • Dòng thứ nhất chứa \(2\) số nguyên dương \(n,k(1\le n\le 10^5,0\le k\le 10^6)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(A_1,A_2,...,A_n(1\le A_i\le 10^6)\)

Output

  • Dòng thứ nhất chứa hai số nguyên \(P\)\(Q\). Trong đó: \(P\) là giá trị \(j-i+1\) lớn nhất có thể cần tìm, và \(Q\) là số lượng cặp \((i,j)\) thoả mãn yêu cầu bài toán.

  • \(Q\) dòng tiếp theo, mỗi dòng in ra các cặp \((i,j)\) thoả mãn yêu cầu bài toán, và in chúng theo thứ tự từ điển. (Cặp \((u_1,v_1)\) được xem là nhỏ hơn cặp \((u_2,v_2)\) nếu \(u_1<u_2\))

Example

Test 1

Input
6 2
21 26 15 0 2 27 
Output
2 1
4 5

Test 2

Input
8 8
2 26 16 27 17 9 29 19
Output
2 1
5 6

Test 3

Input
10 2
25 28 19 27 4 30 29 28 25 9 
Output
3 1
6 8

Test 4

Input
9 0
29 28 4 29 12 12 26 29 23 
Output
2 1
5 6    

Test 5

Input
11 3
10 12 15 12 15 13 16 13 16 0 1
Output
5 2
2 6
5 9

Bình luận

Không có bình luận nào.