Gap

Time limit2sMemory limit512 MB

Summary

Given an increasing sequence of N non-negative integers accessed only through a query function, return the largest gap between consecutive elements.

Level: Medium6 of 10
Topics: Binary search, Implementation, Divide and conquer, Math
Solved: No attempts yet

Problem

There are $N$ non-negative integers $a_1, a_2, \dots, a_N$ satisfying $0 \le a_1 < a_2 < \cdots < a_N \le 10^{18}$ . Jeehak wants to know the largest possible value of $a_{i+1} - a_i$ over $1 \le i \le N-1$ . The input integers are not given directly to Jeehak's program; they are accessible through a special function. See the Implementation section for your chosen programming language for details.

Implement a function that returns the largest possible value of $a_{i+1} - a_i$ over $1 \le i \le N-1$ .

Constraints

In all subtasks, $2 \le N \le 100\,000$ .

Examples1

Example 1
Input
```
2
0 1
```
Expected output
```
1
```