Masala G
Musiqa bloklari
Musiqa studiyasida pleylistdagi treklar ustida mashq qilinmoqda. Pleylistda jami \(n\) ta trek bor va ularning balandlik qiymatlari \(a_1, a_2, \ldots, a_n\) ko'rinishida berilgan.
Pleylistni bir nechta ketma-ket bloklarga ajratish kerak. Har bir blok aynan \(2\) ta yoki aynan \(3\) ta trekdan iborat bo'lishi shart. Har bir trek faqat bitta blokka kiradi va bloklar asl tartibni saqlaydi.
Bir blokning noqulayligi shu blok ichidagi eng katta va eng kichik balandliklar ayirmasiga teng, ya'ni agar blokdagi qiymatlar \(b_1, b_2, \ldots, b_k\) bo'lsa, uning noqulayligi
\[\max(b_1, b_2, \ldots, b_k) - \min(b_1, b_2, \ldots, b_k)\]
bo'ladi.
Sizdan barcha bloklar orasidagi eng katta noqulaylikni imkon qadar kichik qilish so'raladi.
Pleylistni talab qilingan tarzda ajratganda olinishi mumkin bo'lgan eng kichik maksimal noqulaylikni toping.
Birinchi qatorda bitta butun son \(n\) beriladi — treklar soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi — treklarning balandliklari.
Cheklovlar:
\(2 \le n \le 2 \cdot 10^5\)
\(1 \le a_i \le 10^9\)
Bitta butun son chiqaring — mumkin bo'lgan eng kichik maksimal noqulaylik.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 8 4 6 10 9 |
4 |
| 2 |
6 5 5 5 5 5 5 |
0 |
| 3 |
8 3 5 4 9 8 7 1 2 |
2 |
1-misol uchun: pleylistni \((8, 4)\) va \((6, 10, 9)\) bloklariga ajratish mumkin. Birinchi blok noqulayligi \(8 - 4 = 4\), ikkinchi blok noqulayligi \(10 - 6 = 4\). Shuning uchun maksimal noqulaylik \(4\) bo'ladi va bundan kichik javobni olish mumkin emas.
Telegram kanalimizga obuna bo'ling