#include<bits/stdc++.h>
#define LL long long
#define N ((int)1e5 + 8)
#define MAX ((int)1e9 + 8)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define Type pair < int , int >

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // generator


int GetRandomNumber(int a , int b)
{
    return uniform_int_distribution<int>(a, b)(rng); //rand([a,b])
}


Type Opp(Type a , Type b, int type)
{
    if(type == 0) return min(a,b);
    if(type == 1) return max(a,b);
}

int range[N];

void PreProcess(int n , vector < vector < Type > >& tab , vector < int >& arr, int type)
{
    for(int i = 1 ; i <= n ; i++) tab[i][0] = {arr[i] , i};
    for(int p = 1 ; p <= 20 ; p++){
        for(int i = 1 ; i <= n ; i++){
            tab[i][p] = tab[i][p-1];
            ///int L = (i + 2^p - 1) - 2^(p-1) + 1; => i + 2^p - 2^(p-1) => i + 2^(p-1)
            int L = i + (1<<(p-1));
            if(L <= n) tab[i][p] = Opp(tab[i][p] , tab[L][p-1], type);
        }
    }
    /// O(nlogn)


}

void Cal(int n)
{
    range[1] = 0; /// range[len] = p ; 2^p <= len and 2^(p+1) > len
    for(int i = 2 ; i <= n ; i++){
        range[i] = range[i-1];
        if((i & (i-1)) == 0) range[i]++;
        ///range[i] = range[i/2] + 1;
    }
}



Type Query(int L , int R , vector < vector < int > >& tab, int type) /// find minimum, overlapping allowed
{
    if(L > R) return MAX; /// invalid
    int len = R - L + 1;
    int p = range[len];
    ///int i = L + (1<<p) - 1;
    int ans = tab[L][p]; /// green portion
    int i = R - (1<<p) + 1;
    ans = Opp(ans , tab[i][p], type); /// blue portion
    return ans;
} /// O(1)


int main()
{
    /// problem: https://lightoj.com/problem/ghajini
    int n , d;
    cin>>n>>d;
    vector < int > arr(n+1);
    for(int i = 1 ; i <= n ; i++) cin>>arr[i];
    vector < vector < int > > maxTab(n+1 , vector < int >(22)) , minTab(n+1 , vector < int >(22));
    Cal(n);
    PreProcess(n, maxTab , arr, 1);
    PreProcess(n, minTab , arr, 0);

    int ans = 0;
    for(int i = 1 ; i <= n - d + 1 ; i++){
        int L = i , R = i + d - 1;
        int val = Query(L , R , maxTab , 1) - Query(L , R , minTab , 0);
        ans = max(ans , val);
    }
    cout<<ans<<endl;

    /// problem: https://www.spoj.com/problems/MOZPWS/
    vector < int > ans(n - d + 1 + 1);
    for(int i = 1 ; i <= n - d + 1 ; i++){
        int L = i , R = i + d - 1;
        ans[i] = Query(L , R , minTab , 0);
    }

    PreProcess(n - d + 1 , maxTab , ans , 1);

    int q;
    cin>>q;
    while(q--){
        int L , R;
        cin>>L>>R;
        R = R - d + 1;
        if(L > R) cout<<"Impossible\n";
        else cout<<Query(L , R , maxTab , 1);
    }
    return 0;
}



LL Solve(int L , int R, vector < vector < int > >& tab)
{
    if(L > R) return -MAX;
    Type val = Query(L , R , tab , 0);
    int hieght = val.first , pos = val.second;
    LL ans = 1LL*height*(R - L + 1);
    /// O(1)
    return max(ans , max(Solve(L , pos - 1 , tab) , Solve(pos+1 , R , tab)) );
} /// O(n)

int main()
{
    /// problem: https://lightoj.com/problem/histogram
    int n ;
    cin>>n;
    for(int i = 1 ; i <= n ; i++) cin>>arr[i];
    vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22));
    Cal(n);
    PreProcess(n , minTab , arr, 0); /// O(nlogn)
    cout<<Solve(1 , n , minTab, 1)<<endl;
}



LL Solve(int L , int R, vector < vector < int > >& tab , int type)
{
    if(L > R) return 0;
    Type val = Query(L , R , tab , type);
    int hieght = val.first , pos = val.second;
    LL con = 1LL*(pos - L + 1) * (R - pos + 1);
    LL ans = 1LL*height*con;
    /// O(1)
    return ans + Solve(L , pos - 1 , tab , type) + Solve(pos+1 , R , tab , type) ;
} /// O(n)

int main()
{
    /// problem: https://www.spoj.com/problems/DIFERENC/
    int n ;
    cin>>n;
    for(int i = 1 ; i <= n ; i++) cin>>arr[i];
    vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22)) , maxTab(n+1 , vector < Type > (22));
    Cal(n);
    PreProcess(n , minTab , arr, 0); /// O(nlogn)
    PreProcess(n , maxTab , arr, 1); /// O(nlogn)
    cout<<Solve(1 , n , maxTab, 1) - Solve(1 , n , minTab , 0)<<endl;
}