#include <bits/stdc++.h> using namespace std; const int MAXN(5e5 + 5); #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") int n, m; int a[MAXN], dis[MAXN], sum[MAXN]; bool check(int x) { deque<int> s1, s2; int j = 1; for (int i = 1; i <= n; i++) { if (!s1.empty() && s1.front() == i - 1) s1.pop_front(); if (!s2.empty() && s2.front() == i - 1) s2.pop_front(); while (j <= n && (s1.empty() || max(a[s1.front()], a[j]) - min(a[s2.front()], a[j]) <= x)) { while (!s1.empty() && a[j] > a[s1.back()]) s1.pop_back(); while (!s2.empty() && a[j] < a[s2.back()]) s2.pop_back(); s1.emplace_back(j), s2.emplace_back(j); j++; } dis[i] = j - 1; } memset(sum, 0, sizeof sum); sum[n + 1] = 1; for (int i = n; i >= 1; i--) { sum[i] = sum[i + 1]; if (i + m - 1 > dis[i]) continue; if (sum[i + m] - sum[dis[i] + 2] > 0) sum[i]++; } return sum[1] > sum[2]; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", a + i); } int l = 0, r = 1e9, mid; while (l < r) { mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", l); return 0; }