## 题目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John’s flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

## 说明

【样例解释】

【数据范围】

40%的数据：$1 ≤ N ≤ 1000$，$1 ≤ D ≤ 2000$；

100%的数据：$1 ≤ N ≤ 100000$，$1 ≤ D ≤ 1000000$，$0≤x,y≤10^6$。

## 题解

1.队首的一定为最优解
2.弹掉队首不符合条件的点
3.队尾弹掉不比当前插入的点更优的点