Problem D
Meteors

Byteotia is a beautiful, infinite, but very flat and one-dimensional land, which can be represented by the number axis. A meteor shower is about to fall on Byteotia. Thanks to predictions of brilliant Byteotian meteorologists it is known that there will be exactly $n$ meteors. Moreover, it is known exactly when and where each of them will fall: the $i$-th meteor will fall at time $t_ i$ on point $x_ i$.

It is currently time $0$ and Byteasar is at point $0$. Since meteors are dangerous and Byteasar is very much afraid of important data on his laptop (which he always carries with him), he would like to avoid a close encounter with any of them. More precisely, Byteasar would like to maximise his distance from the nearest falling meteor (each distance is measured at the moment of the meteor’s fall).

We assume that Byteasar can run with a speed of at most one unit distance per hour (to the right or to the left) and never gets tired. He can also turn around instantly (and repeatedly).

Help Byteasar save himself and the data on his laptop. Write a program that reads information about falling meteors and determines how far from the nearest meteor Byteasar can travel.

Input

The first line of the input contains one integer $n$ ($1 \le n \le 200\, 000$) specifying the number of falling meteors. The next $n$ lines contain a description of the meteors, one per line. The description of each meteor consists of two integers $t_ i$ and $x_ i$ ($0 \le t_ i \le 10^9$, $-10^9 \le x_ i \le 10^9$) specifying the time and position where the $i$-th meteor will fall.

Output

Your program should output a single real number with precision to one decimal point – the distance of Byteasar from the nearest falling meteor in the optimal solution.

If the result is an integer, you can output it with one zero after the decimal point or without the decimal point.

Explanation of Sample

Byteasar can start running to the right with speed $\frac{1}{2}$, so that at 4 o’clock he will be at position $2$ (and will be $6$ units away from the third meteor), and at 5 o’clock he will be at position $2\frac12$ and at a distance of $5\frac12$ from the first meteor. At that moment Byteasar should turn around and run to the left with maximum speed of $1$, so that at 7 o’clock he will be at the position $\frac12$ (at a distance of $5\frac12$ from the second meteor).

This way Byteasar will always maintain a distance of at least $5\frac12$ from the falling meteor; it is not possible to keep a greater distance than that.

Scoring

The tests are divided into the following subtasks. The tests for each subtask consist of one or more separate test groups.

3
5 -3
7 6
4 -4

5.5