RC5-A. Litsey avtobusi

Litsey avtobusi har kuni ertalab to‘g‘ri ko‘cha bo‘ylab o‘quvchilarni yig‘adi. Ko‘chani son o‘qi deb olamiz: avtobus N ta bekatga belgilangan tartibda kiradi, i-bekat xᵢ nuqtada joylashgan. Bekatlar ko‘cha bo‘ylab tartiblangan bo‘lishi shart emas — avtobus ba’zan orqaga qaytib ham yuradi. Ikki bekat orasidagi yo‘l uzunligi — ular koordinatalari ayirmasining moduli.

Bugun bekatlardan birining oldida ta’mirlash ishlari ketmoqda, shuning uchun haydovchi birinchi va oxirgi bekatdan boshqa istalgan bitta bekatga kirmasdan o‘tib ketadi (qolgan bekatlar tartibi o‘zgarmaydi). Haydovchi bu bekatni eng qulay tanlasa, avtobus eng kamida qancha yo‘l bosadi?

Kirish ma’lumotlari

Birinchi qatorda bitta butun son N — bekatlar soni.

Ikkinchi qatorda N ta butun son x₁, x₂, …, x_N — bekatlar koordinatalari; avtobus ularga shu tartibda kiradi.

Chiqish ma’lumotlari

Bitta butun son — bitta bekat tashlab ketilgandagi eng qisqa yo‘l uzunligi.

Cheklovlar

• 3 ≤ N ≤ 2·10⁵
• −10⁹ ≤ xᵢ ≤ 10⁹ (bir nechta bekat bir nuqtada bo‘lishi mumkin)
• Javob 32 bitli songa sig‘masligi mumkin: C++ da long long ishlating.

1-misol: to‘liq yo‘l 0 → 10 → 3 → 8 → 12, uzunligi 10 + 7 + 5 + 4 = 26. Ikkinchi bekat (10) tashlansa: 0 → 3 → 8 → 12, uzunligi 3 + 5 + 4 = 12.

2-misol: faqat o‘rtadagi bekatni tashlash mumkin: 5 → 7, uzunligi 2.