Range Selection

A set of $n$ integer ranges $($both ends inclusive$)$ of $d$ length each

is given. The starting point of these ranges is given in an array

starts. So the $i^{th}$ range $($starting with zero index$)$ consists of

integers from starts $i$ to starts$[i]+d.$ One integer each is to be

chosen from all of the ranges, subject to the condition that the

difference between any pair of chosen integers is at least dist.

Given the starting points of the ranges, in an array starts, and

the length $d$ of each range, the task is to determine the

maximum possible value of dist such that it is possible to

choose an integer from each of the ranges satisfying the above

condition.

Example

Suppose $n=3,d=2$ and starts $=[3,2,3].$

The given ranges are $-\left[\begin{array}{cc}3& 5\\ 2& 4\\ 3& 5\end{array}\right]$

One integer each has to be chosen from the given ranges such

that the difference between any pair of chosen integers is at

least dist. The aim is to maximize such an integer dist.

It is optimal to choose dist $=1.$

The integer $3$ can be chosen from the $1^{st}$ range $-3,5(1-$based

indexing$)$

The integer $2$ can be chosen from the $2^{nd}$ range $-[2,4]$

The integer $4$ can be chosen from the $3^{rd}$ range $-3,5$

The difference between any pair of chosen integers is at least

So $1$ is the maximum possible value of dist.

least dist. The aim is to maximize such an integer dist.

It is optimal to choose dist $=1.$

The integer $3$ can be chosen from the $1^{st}$ range $-3,5(1-$based

indexing$)$

The integer $2$ can be chosen from the $2^{nd}$ range $-2,4$

The integer $4$ can be chosen from the $3^{rd}$ range $-3,5$

The difference between any pair of chosen integers is at least

So $1$ is the maximum possible value of dist.

Function Description

Complete the function getMaxDist in the editor below.

getMaxDist has the following parameters:

long starts$[$n$]$: the starting points of all the ranges

long $d$ : the length of each range

Returns

long int: the maximum possible value of dist such that it is

possible to choose an integer from each of the given ranges

satisfying the given condition.

Constraints

$2n{10}^5$

$1$ starts $[i]{10}^{14}$

$1d{10}^{14}$

Input Format For Custom Testing

solve it in c$++$