In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house. 
The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house. 
The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints: 
1. All houses are to be moved along a one-dimensional path. 
2. Houses must be moved at integer locations along the path, with no two houses at the same location. 
3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order. 
4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter). 
Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training. 

3

4 4

20 30 10 40

5 6

20 34 54 10 15

4 2

10 20 16 13 

Case 1: 3

Case 2: 3

Case 3: -1

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

const int inf=;

struct in { int ht,op; } s[maxn];

bool cmp(in a,in b){ return a.ht<b.ht;}

int Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt,n;

int dis[maxn],vis[maxn],inq[maxn];

int S,E;

void update()

{

    cnt=;

    memset(Laxt,,sizeof(Laxt));

    memset(vis,,sizeof(vis));

    memset(inq,,sizeof(inq));

}

void add(int u,int v,int d)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    Len[cnt]=d;

}

bool spfa()

{

    for(int i=;i<=n+;i++)  dis[i]=inf;

    queue<int>q;

    q.push(S); dis[S]=; inq[S]=;

    while(!q.empty()){

        int u=q.front(); q.pop(); inq[u]=;

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i];

            if(dis[v]>dis[u]+Len[i]){

                dis[v]=dis[u]+Len[i];

                if(!inq[v]){

                   inq[v]=;

                   vis[v]++;

                   q.push(v);

                   if(vis[v]>n+) return false;

                }

            }

        }

    } return true;

}

int main()

{

    int T,i,d,Case=;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&d);

        update();

        for(i=;i<=n;i++) scanf("%d",&s[i].ht), s[i].op=i;

        sort(s+,s+n+,cmp);

        for(i=;i<n;i++){

            add(i+,i,-);

            if(s[i+].op>s[i].op) add(s[i].op,s[i+].op,d);

            else add(s[i+].op,s[i].op,d);

        }

        S=s[].op; E=s[n].op;

        if(S>E) swap(S,E);   //才符合最远，左起右终。

        printf("Case %d: ",++Case);

        if(spfa()) printf("%d\n",dis[E]);

        else printf("-1\n");

    } return ;

}

//求最长，小于，最短路算法。