Bạn được cho ~n~ tòa nhà cao tầng nằm trên cùng một đường thẳng. Tòa nhà thứ ~i~ có chân tại vị trí ~x_i~ (theo trục ngang) và chiều cao ~y_i~. Trụ sở đội đặc nhiệm ở tòa nhà ~1~, tòa nhà cần đột nhập là tòa nhà ~n~. Các mái nhà tương ứng là các điểm ~(x_i, y_i)~ trong mặt phẳng.

Từ mái một tòa nhà, đội có thể bắn dây móc thẳng tới mái một tòa nhà khác và di chuyển theo dây. Dây móc là một đoạn thẳng nối hai mái nhà và có thể thu hồi sau khi tới nơi (nên có thể thực hiện nhiều lần bắn dây).

Một lần di chuyển từ tòa nhà ~i~ tới tòa nhà ~j~ là hợp lệ nếu đoạn thẳng nối hai điểm ~(x_i, y_i)~ và ~(x_j, y_j)~ không chạm vào bất kỳ tòa nhà nào khác.

Mỗi tòa nhà ~k~ được xem như một đoạn thẳng đứng tại ~x = x_k~ từ độ cao ~0~ đến ~y_k~. Vì vậy, khi bắn dây từ ~i~ tới ~j~ (giả sử ~x_i < x_j~), yêu cầu tương đương là: với mọi ~k~ thỏa ~x_i < x_k < x_j~, độ cao của dây tại hoành độ ~x_k~ phải lớn hơn ~y_k~ (không được bằng).

Yêu cầu

Hãy xác định độ dài dây móc ngắn nhất cần có để đội có thể đi từ tòa nhà ~1~ tới tòa nhà ~n~ (có thể qua các tòa trung gian), trong đó mỗi lần bắn dây phải là một đoạn thẳng hợp lệ như mô tả trên.

Dữ liệu

• Dòng 1: số nguyên ~n~.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~, ~y_i~.

Kết quả

In ra một số thực — độ dài dây móc ngắn nhất cần có, với độ chính xác ~10^{-10}~.

Ví dụ

Ví dụ 1

Input

3
0 10
5 15
10 10

Output

7.071068

Giải thích

Ví dụ 1

Có thể di chuyển từ tòa nhà ~1~ tới tòa nhà ~2~ (hoặc từ ~2~ tới ~3~) bằng dây móc không chạm tòa nhà còn lại. Độ dài ngắn nhất cần có là độ dài lớn nhất trong các lần bắn dây trên một lộ trình tối ưu, bằng ~\sqrt{(5-0)^2 + (15-10)^2} = \sqrt{50} \approx 7.071068~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^5~
• ~0 \le x_i < x_{i+1} \le 10^9~
• ~0 \le y_i \le 10^9~