题目描述

译自 POI 2010 Stage 3. Day 2「Pilots」

给定序列 $a_1, a_2, ..., a_n$ 和整数 $t$，求最长的子串 $a_i, ..., a_j$，使得对子串中任意两个元素 $a_k, a_l$，有 $|a_k - a_l| \le t$。

输入格式

第一行两个整数 $t$ 和 $n$，用空格分隔。 第二行表示序列 $a_i$，用空格分隔，每个数在 $1$ 到 $2000000000$ 之间。

输出格式

输出一个整数，表示最长的子串长度。

3 9
5 1 3 5 8 6 6 9 10

4

有两个符合要求的最长子串，长度均为 $4$，分别是 $5,8,6,6$ 和 $8,6,6,9$。

数据范围与提示

对于 $100\%$ 的数据， $0 \le t \le 2000000000, 1\le n \le 3000000$ 。

Translated by vincent163