آنتن‌های خیابان ولیعصر قدیمی شده‌اند و تعویض آن‌ها ضروری است. آنتن‌های جدیدی که در بازار هستند، چینی‌اند و تنها می‌توانند در یک جهت (چپ و یا راست) سیگنال را رد و بدل کنند (آنتن‌های غیر چینی دو طرفه هستند). محدوده‌ی دید آنتن به معنای مجموعه نقاطی است که آنتن می‌تواند به آن‌ها سیگنال بفرستد و یا سیگنالی از آن‌ها دریافت کند. محدوده‌ی دید یک آنتن بر حسب مکان، جهت و شعاع دیدش تعیین می‌شود. اگر مکان آنتن را نقطه‌ی $x$، شعاع دیدش را $R$ و جهتش را به سمت چپ بگیریم، محدوده‌ی دید آنتن برابر با $[x-R,x]$ است و در صورتی که جهت آنتن به سمت راست باشد، محدوده‌ی دید آن برابر با $[x,x+R]$ می‌شود.

دو آنتن $x$ و $y$ می‌توانند با یکدیگر ارتباط برقرار کنند اگر و فقط اگر دنباله‌ای از آنتن‌ها مانند $a_0,a_1,a_2,…,a_k$ وجود داشته باشد به طوری که $a_0=x$ و $a_k=y$ باشد و به ازای تمامی $i$هایی که $0\leq i\leq k-1$، آنتن $a_i$ در محدوده‌ی دید $a_{i+1}$ و آنتن $a_{i+1}$ در محدوده‌ی دید $a_i$ باشد.

با این فرض که شعاع دید تمامی آنتن‌ها باید یکسان باشد، برنامه‌ای بنویسید که با گرفتن مکان اولیه‌ی آنتن‌ها، کم‌ترین شعاع دید لازم را به منظور مرتبط کردن تمام آنتن‌ها با یکدیگر، پیدا کند. در واقع کم‌ترین شعاع دیدی که حداقل یک جهت‌دهی برای آن وجود دارد که در آن هر دو آنتنی می‌توانند با هم ارتباط برقرار کنند.

در سطر اول ورودی عدد طبیعی $n$، تعداد آنتن‌ها، آمده است.($1\leq n \leq 10^6$)

سطر دوم شامل $n$ عدد طبیعی $x_1,x_2,…,x_n$ است که $x_i$ نمایانگر مکان آنتن $i$- ام است.($0\leq x_1,x_2,…,x_n\leq 10^9$)

در تنها سطر خروجی باید کم‌ترین شعاع لازم برای مرتبط کردن همه‌ی آنتن‌ها با یکدیگر چاپ شود.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد