Broadcast Tower Buffer Zone

A regional radio network has installed n broadcast towers on a flat coordinate plane, each at integer coordinates (x, y). To reduce interference, engineers want the widest possible north-south buffer corridor — a vertical strip of some width w, lying between the leftmost and rightmost towers — that contains no tower strictly inside it (a tower may sit exactly on either edge of the strip). Two or more towers may share the same coordinates. Given the tower positions, find the maximum possible width w of such a corridor.

Input format

• Line 1: an integer n — the number of towers.
• Each of the next n lines contains two integers x and y — the coordinates of one tower.

Output format

Print a single integer: the maximum width of a vertical corridor, lying between the leftmost and rightmost tower, that contains no tower strictly inside it.

Constraints

• 2 <= n <= 10^4
• 0 <= x, y <= 10^9

5
8 7
9 9
7 4
9 7
4 3

3

2
3 1
9 0

6