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)\) và \((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\) và \(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