The Ninja Way

As everyone knows, ninjas travel by leaping from treetop to treetop. A ninja clan plans to use $N$ trees to practice tree-hopping. They start on the shortest tree and make $N-1$ jumps, each jump landing on a tree taller than the one they leave. When they finish, they will have stood on every tree exactly once, visiting the trees in increasing order of height and ending on the tallest tree.

A ninja can cover at most a fixed horizontal distance $D$ in a single jump. To make the training as fun as possible, the clan wants to maximize the horizontal distance between the shortest tree and the tallest tree.

The trees are planted subject to the following rules:

• All trees stand along a single one-dimensional path.
• Each tree occupies an integer position on the path, and no two trees share a position.
• The left-to-right order of the trees must match the order given in the input. The trees are NOT sorted by height or rearranged in any way; they keep their given order.
• Because a ninja can only jump so far, every tree must be planted close enough to the next taller tree: the two horizontal positions may differ by at most $D$ (the difference in their heights does not matter).

Given $N$ trees in a fixed order, each with a distinct integer height, determine the maximum possible horizontal distance between the shortest tree and the tallest tree.

The input contains several test cases. Each test case starts with a line containing two integers $N$ ($1 \le N \le 1000$) and $D$ ($1 \le D \le 10^6$). The next $N$ lines each contain one integer, the height of a tree, listed in the order the trees must be planted. Within a test case all heights are distinct. The list of test cases ends with a line containing two zeros (0 0), which is not processed.

For each test case, print a single line with one integer: the maximum horizontal distance between the shortest and the tallest tree that respects all of the rules above, or -1 if no valid layout exists. Do not print any blank lines between answers.