Лосеня

Нещодавно на околиці Великого Резервату Рівнин з'явився чарівний ліс, і дуже допитливий молодий лось вирішив його дослідити. Після кількох годин блукання серед зачарованих дерев молодий лось вийшов із лісу, вже значно менш допитливий. Однак, повернувшись додому, лось помітив, що його роги значно розширилися. Оскільки більші роги означають більший вплив у лосиному суспільстві, інші лосі зажадали докладної карти чарівного лісу від молодого лося.

За словами молодого лося, який, на диво, все пам'ятав, ліс розділений на $N$ паралельних рядів, у $i$-му ряду росте k_i дерев. Лось точно запам'ятав відстані між сусідніми деревами у кожному ряду. Оскільки ліс чарівний, коли лось проходив між деревами з відстанню $d$ між ними, його роги розширювалися до $d$.

Через свою прямолінійність та дбайливе ставлення до рогів усі лосі погодилися, що можна рухатися через чарівний ліс лише вперед — з рядка $i$ до i+1. Жоден лось не може пройти між деревами, якщо відстань між ними менша за ширину його рогів. Тепер усім лосям, особливо тим, у кого вузькі роги, цікаво, якої максимальної ширини можуть бути роги лося, коли він вийде з лісу, якщо перед входом у ліс ширина його рогів дорівнювала нулю.