#include <bits/stdc++.h> using namespace std; #define ONLINE #ifndef ONLINE #define debug(...) fprintf(stderr, ##__VA_ARGS__) #else #define debug(...) ; #endif using LL = long long; using PII = pair<int, int>; #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend() //快读 template <typename T> inline T READ() { T x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f |= (c == '-'), c = getchar(); while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); return f ? -x : x; } inline int read() { return READ<int>(); } inline LL readLL() { return READ<LL>(); } mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); #define N 500010 namespace ST_C { // Sparse Table Constant vector<int> Logn; void init(int maxn = N) { Logn.resize(maxn); Logn[1] = 0, Logn[2] = 1; for (int i = 3; i < maxn; i++) { Logn[i] = Logn[i / 2] + 1; } } } // namespace ST_C template <typename T> class ST { using VT = vector<T>; using VVT = vector<VT>; using func_t = function<T(const T&, const T&)>; // RMQ函数，也可以用lambda表达式 VVT a; // a is Sparse Table func_t op; public: ST() {} ST(const vector<T>& v, int n, func_t func) { init(v, n, func); // v的有效下标为 1~n } void init(const vector<T>& v, int n, func_t func) { op = func; // e.g. int mx_l = ST_C::Logn[n] + 1; // max log a.assign(n + 1, VT(mx_l, 0)); for (int i = 1; i <= n; i++) { a[i][0] = v[i]; } for (int j = 1; j < mx_l; j++) { int p = (1 << (j - 1)); for (int i = 1; i + p <= n; i++) { a[i][j] = op(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]); } } } T query(int l, int r) { int lt = r - l + 1; int p = ST_C::Logn[lt]; return op(a[l][p], a[r - (1 << p) + 1][p]); } }; template <typename T> // T is int or LL class FenTree { private: int n; vector<T> c; inline int lowbit(const int& x) { return x & (-x); } public: FenTree() {} FenTree(int n_) { init(n_); } void init(int n_) { c.assign(n = n_, T(0)); } void add(int i, int x) { for (; i < n; i += lowbit(i)) c[i] += x; } T query(int i) { if (i <= 0) return 0; T res = 0; for (; i; i -= lowbit(i)) res += c[i]; return res; } }; int main() { ST_C::init(); //初始化 int n = read(), m = read(); vector<int> a(n + 1), dp; FenTree<int> fen; for (int i = 1; i <= n; i++) a[i] = read(); auto max_int = [](const int& x, const int& y) -> int { return x > y ? x : y; }; auto min_int = [](const int& x, const int& y) -> int { return x < y ? x : y; }; ST<int> mx(a, n, max_int), mn(a, n, min_int); auto check = [&](const int& lim) -> bool { debug("lim=%d\n", lim); dp.assign(n + 1, 0); dp[0] = 1; fen.init(n + 1); for (int i = 1, opt = 1; i <= n; i++) { while (mx.query(opt, i) - mn.query(opt, i) > lim) opt++; if (i < m) continue; debug("\t\ti=%d opt=%d %d\n", i, opt, i - opt + 1); if (i - opt + 1 < m) continue; debug("\t\tquery(%d,%d)\n", opt - 1, i - m); if (opt == 1 || fen.query(i - m) - fen.query(opt - 2) > 0) { debug("\tdp[%d]=1 opt=%d\n", i, opt); dp[i] = 1; fen.add(i, 1); } } return dp[n] > 0; }; int l = 0, r = 1e9, mid, ans = 1e9; while (l <= r) { mid = l + r >> 1; if (check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans; return 0; }