p02543 ACL Contest 1 - Keep Distances_32035
There are N points on a number line, i-th of which is placed on coordinate X_i. These points are numbered in the increasing order of coordinates. In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds. In addition to that, an integer K is given.

Process Q queries.

In the i-th query, two integers L_i and R_i are given. Here, a set s of points is said to be a good set if it satisfies all of the following conditions. Note that the definition of good sets varies over queries.

* Each point in s is one of X_{L_i},X_{L_i+1},\ldots,X_{R_i}.
* For any two distinct points in s, the distance between them is greater than or equal to K.
* The size of s is maximum among all sets that satisfy the aforementioned conditions.



For each query, find the size of the union of all good sets.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq K \leq 10^9
* 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
* 1 \leq Q \leq 2 \times 10^5
* 1 \leq L_i \leq R_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
X_1 X_2 \cdots X_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q


Output

For each query, print the size of the union of all good sets in a line.

Examples

Input

5 3
1 2 4 7 8
2
1 5
1 2


Output

4
2


Input

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12


Output

4
6
11
2
3
#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

//INSERT ABOVE HERE
const Int LOG = 20;
const Int MAX = 2e5+10;
Int nx[LOG][MAX]={};
Int sm_nx[LOG][MAX]={};

Int pr[LOG][MAX]={};
Int sm_pr[LOG][MAX]={};
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n,k;
  cin>>n>>k;
  auto xs=read(n);
  xs.emplace(xs.begin(),-k);
  xs.emplace_back(Int(xs.back())+k);

  for(Int i=1;i<=n;i++){
    nx[0][i]=lower_bound(xs.begin(),xs.end(),xs[i]+k)-xs.begin();
    pr[0][i]=--upper_bound(xs.begin(),xs.end(),xs[i]-k)-xs.begin();
    sm_nx[0][i]=i;
    sm_pr[0][i]=i+1;
  }

  nx[0][n+1]=n+1;
  pr[0][0]=0;

  for(Int k=0;k+1<LOG;k++){
    for(Int i=0;i<=n+1;i++){
      nx[k+1][i]=nx[k][nx[k][i]];
      pr[k+1][i]=pr[k][pr[k][i]];
      sm_nx[k+1][i]=sm_nx[k][i]+sm_nx[k][nx[k][i]];
      sm_pr[k+1][i]=sm_pr[k][i]+sm_pr[k][pr[k][i]];
    }
  }

  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int l,r;
    cin>>l>>r;
    // [l, r]
    Int p=l,q=r;
    Int ans=0;
    // cout<<l<<newl;
    // cout<<r<<newl;
    for(Int k=LOG-1;k>=0;k--){
      if(nx[k][p]<=r){
        ans-=sm_nx[k][p];
        p=nx[k][p];
        // cout<<p<<newl;
      }
      if(pr[k][q]>=l){
        ans+=sm_pr[k][q];
        q=pr[k][q];
        // cout<<q<<newl;
      }
    }
    // cout<<":";
    ans-=p;
    ans+=q+1;
    cout<<ans<<newl;
  }

  return 0;
}
