1 /************************************************************** 2     Problem: 2096 3     User: rausen 4     Language: C++ 5     Result: Wrong_Answer 6 ****************************************************************/ 7   8 #include <cstdio> 9 #include <algorithm>10  11 using namespace std;12 const int N = 3000005;13 const int Maxlen = 12 * N + 105;14  15 int n, k, ans = 1;16 int a[N], q[2][N], l[2], r[2];17 char buf[Maxlen], *c = buf;18 int Len;19  20 inline int read() {21     int x = 0, sgn = 1;22     while (*c < ‘0‘ || ‘9‘ < *c) {23             if (*c == ‘-‘) sgn = -1; 24             ++c;25         }26     while (‘0‘ <= *c && *c <= ‘9‘)27         x = x * 10 + *c - ‘0‘, ++c;28     return sgn * x;29 }30  31 inline void pop_tail_max(int i) {32     while (l[0] <= r[0] && a[q[0][r[0]]] <= a[i])33         --r[0];34     q[0][++r[0]] = i;35 }36  37 inline void pop_tail_min(int i) {38     while (l[1] <= r[1] && a[q[1][r[1]]] >= a[i])39         --r[1];40     q[1][++r[1]] = i;41 }42  43 int main() {44     int i, tmp;45     Len = fread(c, 1, Maxlen, stdin);46     buf[Len] = ‘\0‘;47     k = read(), n = read();48     for (i = 1; i <= n; ++i)49         a[i] = read();50     l[0] = l[1] = 1;51     for (i = 1; i <= n; ++i) {52         pop_tail_min(i);53         pop_tail_max(i);54         while (a[q[0][l[0]]] - a[q[1][l[1]]] > k)55             if (q[0][l[0]] < q[1][l[1]]) tmp = q[0][l[0]++] + 1;56             else tmp = q[1][l[1]++] + 1;57         ans = max(ans, i - tmp + 1);58     }59     printf("%d\n", ans);60     return 0;61 }