Obeleži sve kategorije koje odgovaraju problemu

Постоји $n$ локација на $x$-оси на које је могуће поставити предајник. На располагању су два предајника са дометом $d$. Потребно је поставити их тако да буду што више размакнути како би покривеност била што већа, али и да буду на раздаљини највише $d$ како би могли међусобно да комуницирају. Написати програм који одређује максималну раздаљину између предајника. Временска сложеност треба да буде $O(n \log n)$, а просторна $O(n)$.

Улаз

Са стандардног улаза се уноси број $n$ ($n \leq 10^5$) и затим се уноси $n$ целих бројева из интервала $[-10^9, 10^9]$ који представљају координате тачака на $x$-оси где је могуће сместити предајнике. На крају се уноси број $d$ ($d \leq 10^9$).

Излаз

На стандардни излаз исписати један број који представља тражену раздаљину.

Пример

Улаз

4
7 3 1 8
3

Излаз

2