Đoạn ổn định (Stable Segment)

Phiên bản: Phước Hưng OJ

Đề bài

Cho dãy $A$ gồm $N$ số nguyên $A_1,A_2,\ldots,A_N$ và số nguyên không âm $K$.

Với $1\le L\le R\le N$, đoạn liên tiếp $A_L,A_{L+1},\ldots,A_R$ được gọi là ổn định nếu

$$\max_{L\le i\le R} A_i-\min_{L\le i\le R} A_i\le K.$$

Hãy tìm độ dài lớn nhất $D$ của một đoạn ổn định và số lượng $C$ đoạn ổn định có độ dài đúng bằng $D$.

Input

• Dòng đầu chứa hai số nguyên $N,K$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra hai số nguyên $D,C$ trên cùng một dòng, cách nhau bởi một dấu cách.

Subtask

• Subtask 1 (30%): $1\le N\le 3000$, $0\le K\le 2\times 10^9$, $|A_i|\le 10^9$.
• Subtask 2 (30%): $1\le N\le 2\times 10^5$, $0\le K\le 2\times 10^9$, $|A_i|\le 10^9$ và dãy $A$ không giảm.
• Subtask 3 (40%): $1\le N\le 2\times 10^5$, $0\le K\le 2\times 10^9$, $|A_i|\le 10^9$.

Ví dụ

Ví dụ 1

Input

6 3
1 3 5 4 2 6

Output

4 1

Giải thích

Đoạn $[2,5]$ gồm $3,5,4,2$ có hiệu giữa giá trị lớn nhất và nhỏ nhất bằng $3$. Đây là đoạn ổn định dài nhất và chỉ có một đoạn như vậy.

Ví dụ 2

Input

4 0
4 4 4 4

Output

4 1

Giải thích

Cả dãy là một đoạn ổn định có độ dài $4$.

Ví dụ 3

Input

5 1
1 10 2 9 3

Output

1 5

Giải thích

Không có hai phần tử kề nhau nào tạo thành đoạn ổn định độ dài $2$, nên độ dài lớn nhất là $1$ và có $5$ đoạn.