← 返回题目列表

Codeforces · 6/E

E. 博览会

中文机器翻译题面 查看原题

距离贝尔兰著名作家贝尔伯里的五十岁生日还有几天。为此,当地图书馆决定对这位著名科幻作家的作品进行展览。还决定有必要将那些在特定时期出版的书籍纳入博览会。显然,如果书籍的尺寸相差太大,参观者就不会喜欢它。因此,组织者认为,博览会上最高和最低的书籍之间的差异不应超过k毫米。

图书馆有 n 卷 Berlbury 的书籍,按出现的时间顺序排列。每本书的高度(以毫米为单位)是已知的,很嗨。由于伯伯里在这座城市备受推崇,组织者希望在博览会中收录尽可能多的书籍,并了解他们将设法涵盖他的哪些时期的创作作品。您被要求帮助组织者应对这项艰巨的任务。

输入

输入数据的第一行包含两个由空格分隔的整数 n (1 ≤ n ≤ 105) 和 k (0 ≤ k ≤ 106) — Berlbury 图书馆的图书数量,以及最低和最高图书之间允许的最大高度差。第二行包含 n 个整数,用空格分隔。每个数字 hi (1 ≤ hi ≤ 106) 是第 i 本书的高度(以毫米为单位)。

输出

输出数据的第一行打印两个数字a和b(用空格分隔),其中a是组织者可以包含在博览会中的最大书籍数量,b是Berlbury出版书籍的时间段数量,并且这些书籍中最低和最高的高度差不超过k毫米。

在接下来的 b 行中,每行打印两个由空格分隔的整数 — Berlbury 创造性工作的每个所需时间段的第一卷和最后一卷的索引。

示例

输入 #1

3 3
14 12 10

输出 #1

2 2
1 2
2 3

输入 #2

2 0
10 10

输出 #2

2 1
1 2

输入 #3

4 5
8 19 10 13

输出 #3

2 1
3 4