Olimpiya ölkəsinin mərkəzi bağçası o qədər böyükdür ki, bir bağbanın ona qulluq etməyə gücü çatmır. Bağı iki sahəyə ayırmaq qərarı verildi. Müəyyən ağaclar birinci sahəyə, qalanlar isə ikinci sahəyə daşınacaq. Bağın ayrılmış sahələrindən biri boş qala bilər.

Hər bir ağac cütlüyü arasında cığır açıldı. Bağbanlar bir ağacdan digərinə mütləq bu iki ağacı birləşdirən cığırla getməlidirlər. Hər iki hərəkət istiqamətində cığırların uzunluğu eynidir.

Bağbanların işini sadələşdirmək üçün bölməni elə aparmaq qərarına gəldilər ki, eyni bir sahədə olan ağaclar cütlüyü arasındakı məsafə minimal olsun.

Bütün ağac cütlükləri arasındakı cığırların uzunluqları haqqında verilmiş informasiyaya əsasən, optimal bölgü aparıldıqdan sonra bağın bir sahəsində olan iki ağac arasındakı ən uzun cığırın uzunluğunu təyin edən proqram yazın.

Giriş verilənləri

İlk sətirdə bağdakı ağacların n (2 ≤ n ≤ 1000) sayı verilir. Növbəti n - 1 sətrin hər bir i-ci sətri ardıcıl olaraq i-ci ağac ilə i + 1-dən n-ə qədər ağaclar arasındakı cığırların uzunluqlarını ifadə edən n - i sayda ədəd ehtiva edir. Bütün ədədlər tam ədədlərdir, mənfi deyillər, 106-nı aşmırlar.

Çıxış verilənləri

Bütün mümkün bölgülərdə bağın bir sahəsində olan iki ağac arasındakı ən uzun cığırlardan ən kiçik olanı ifadə edən yeganə tam ədədi verməli.