TP-O3. Hamma uchun qulay vaqt

k ta o‘qituvchi bor, i-o‘qituvchi bo‘sh bo‘ladigan daqiqalar ro‘yxati berilgan (o‘sish tartibida). Direktor [L; R] vaqt oralig‘ini tanlamoqchi: har bir o‘qituvchining kamida bitta bo‘sh daqiqasi shu oraliqqa tushsin. Oraliq iloji boricha qisqa bo‘lsin. R − L ning eng kichik qiymatini toping.

Barcha daqiqalarni o‘qituvchi raqami bilan bitta saralangan ro‘yxatga birlashtiring va oynani yurgizing.

Kirish ma’lumotlari

Birinchi qatorda k. Keyingi k qatorning har birida avval mᵢ, keyin mᵢ ta daqiqa (o‘sish tartibida).

Chiqish ma’lumotlari

Bitta son — R − L ning eng kichik qiymati.

Cheklovlar

1 ≤ k ≤ 10⁵; mᵢ ≥ 1; Σmᵢ ≤ 2·10⁵; 0 ≤ daqiqa ≤ 10⁹.