Description

There are $N$ strictly increasing nonnegative integers $a_1, a_2, \dots, a_N$ with $0 \leq a_1 < a_2 < \cdots < a_N \leq 10^{18}$. You need to find the maximum value among $a_{i + 1} - a_i$ for $1 \leq i \leq N - 1$.

Your program cannot read this integer sequence directly, but you can query information about the sequence through the provided function. Please refer to the implementation details below for your language.

You must implement a function that returns the maximum value of $a_{i + 1} - a_i$ for $1 \leq i \leq N - 1$.

Judging method The following judging method applies. If this differs from the main statement, this section prevails.

• Your code must not include the gap.h library.
• You must declare the functions findGap and MinMax as follows:

extern "C" void MinMax(long long,long long,long long*,long long*);
extern "C" long long findGap(int,int);

• spj and interaction library
• If you encounter issues, please contact the problem provider.

Implementation details

This problem only supports C++ (including cpp11, cpp14, cpp17).

You must implement a function findGap(T, N), which takes the following parameters and returns a value of type long long:

• $T$: subtask ID ($1$ or $2$).
• $N$: the length of the sequence.

Your function findGap may call the system-provided query function MinMax(s, t, &mn, &mx). The first two parameters $s$ and $t$ are of type long long, and the last two parameters &mn and &mx are pointers to long long (mn and mx are long long variables). When MinMax(s, t, &mn, &mx) returns, mn will store the minimum $a_i$ such that $a_i \in [s, t]$, and mx will store the maximum $a_i$ such that $a_i \in [s, t]$. If there is no number from the sequence in the interval $[s, t]$, both mn and mx will be set to $-1$. You must ensure $s \leq t$ when querying; otherwise, the program will terminate and the test will receive a score of $0$.

Sample 1

C/C++

Consider $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$.

The answer should be $3$, which can be obtained using the following queries to MinMax:

• Call MinMax(1, 2, &mn, &mx), then both mn and mx return $2$.
• Call MinMax(3, 7, &mn, &mx), then mn returns $3$, and mx returns $6$.
• Call MinMax(8, 9, &mn, &mx), then both mn and mx return $8$.

Sample judging method

The sample judge reads two lines from standard input. The first line contains two integers, the subtask ID $T$ and the sequence length $N$. The second line contains $N$ strictly increasing nonnegative integers. Then the program writes two lines to standard output: the first line is the return value of findGap, and the second line is the value of the cost $M$.

The following input describes the sample above:

2 4
2 3 6 8

Note that the actual interaction library and spj encrypt the testdata.

Constraints and agreements

For all test cases, $2 \leq N \leq 100000$.

Before each test case starts, $M$ will be initialized to $0$.

Subtask 1 (30 points): Each call to MinMax increases $M$ by $1$. To receive full points, you must ensure $M \leq \frac{N + 1}{2}$ for all test cases in this subtask.

Subtask 2 (70 points): Let $k$ be the number of sequence elements within the interval $[s, t]$ for a MinMax call. Each call to MinMax increases $M$ by $k + 1$. For each test case, if $M \leq 3N$, you will receive 70 points; otherwise, you will receive $\dfrac{60}{\sqrt{\frac MN + 1} - 1}$ points. Your score for this subtask is the minimum over all its test cases.

Hint

Translated by ChatGPT 5