Let \(f_{i,j}\) denote the maximum value in the interval \([j, j+2^i-1]\) of the current array \(a\), and let \(g_{i,j}\) denote the minimum value in the interval \([j, j+2^i-1]\). The initial conditions are: \( f_{0,i}=g_{0,i}=a_i. \) The transitions are:

• \( f_{i,j}=\max\bigl(f_{i-1,j}, f_{i-1,j+2^{i-1}}\bigr), \)
• \( g_{i,j}=\min\bigl(g_{i-1,j}, g_{i-1,j+2^{i-1}}\bigr). \)

To query the maximum over an interval \([l,r]\), let \( k=\left\lfloor \log_2(r-l+1)\right\rfloor. \) Then the maximum on \([l,r]\) is: \( \max\bigl(f_{k,l}, f_{k,r-2^k+1}\bigr). \) Similarly, the minimum on \([l,r]\) is: \( \min\bigl(g_{k,l}, g_{k,r-2^k+1}\bigr). \)

After building the \(f\) and \(g\) tables, enumerate all intervals of length \(K\), i.e. \([l,r]\), compute the difference between the maximum and minimum within each interval, and take the maximum of these differences as the answer. The preprocessing time complexity is \(O(n\log n)\), and the answer computation is \(O(n)\), so the total time complexity is \(O(n\log n)\), which can pass this problem.

(In the code, the two dimensions of the DP arrays are swapped.)

namespace Loyalty
{
    int a[N], lg[N], f[N][20], g[N][20];
    inline int qmax(int l, int r)
    {
        int lgx = lg[r - l + 1];
        return max(f[l][lgx], f[r-(1 <<lgx) + 1][lgx]);
    }
    inline int qmin(int l, int r)
    {
        int lgx = lg[r - l + 1];
        return min(g[l][lgx], g[r - ( 1<< lgx ) + 1][lgx]);
    }
    inline void init() {}
    inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
    {
        int n, k;
        cin >> n >> k; lg[0] = -1;
        for (int i = 1; i <= n; ++i)
            cin >> a[i], f[i][0] = g[i][0] = a[i];
        for (int i = 1; i <= n; ++i)
            lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i < 20; ++i)
            for (int j = 1; j <= n - (1 << i) + 1; ++j)
                f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]), 
                g[j][i] = min(g[j][i - 1], g[j + (1 << (i - 1))][i - 1]);
        int mx = 0;
        for (int i = 1, j = k; j <= n; ++i, ++j)
            mx = max(mx, qmax(i, j) - qmin(i, j));
        cout << mx << '\n';
    }
} // namespace Loyalty