N ширхэг чулуу байна, тэдгээр нь 1, 2, ..., N гэж дугаарлагдсан. Чулуу бүрийн өндөрийг \(h_i\) гэж өгсөн.

Мөн дараах нөхцөл биелнэ:

• \(h_1 < h_2 < ⋯ < h_N\)

(өөрөөр хэлбэл, чулуунуудын өндөр өсөх дарааллаар эрэмбэлэгдсэн)

Мэлхий эхлээд 1-р чулуу дээр байрлана. Тэрээр дараах үйлдлийг хэд хэдэн удаа давтан хийж байж N-р чулуу дээр хүрнэ:

• Хэрэв мэлхий одоогоор i-р чулуу дээр байгаа бол, i+1, i+2, ..., i+N гэсэн чулуунуудын аль ч чулуу руу үсэрч болно.
• Үсэрч буухад \((h_j - h_i)^2 + C\) гэсэн зардал гарна (\(j\) нь буусан чулуу).

Мэлхий N-р чулуу дээр хүрэхэд гарах нийт зардлын хамгийн бага боломжит утгыг ол.

Оролт:

Оролтын файлын эхний мөрөнд чулуунуудын тоо болох N, үсрэхэд тооцоологдор C бүхэл тоо өгөгдөнө.

Хоёр дахь мөрөнд чулуунуудын өндөрийг илэрхийлэх h1 h2 … hN гэсэн N ш бүхэл тоонууд хоосон зайгаар тусгаарлан өгөгдөнө.

Гаралт:

Гарах боломжтой хамгийн бага нийт зардлыг хэвлэ.

Хязгаарлалтууд:

• Оролтын бүх утгууд нь бүхэл тоо байна.
• \(2≤N≤2×10^5\)
• \(1≤?≤10^{12}\)
• \(1≤h1​<h2​<⋯<hN​≤10^6\)

Дэд бодлого

Жишээ:

Оролт-1

5 6
1 2 3 4 5

Гаралт-1

20

Тайлбар-1

Зам:

1 → 3 → 5

Өртөг:

(3-1)² + 6 = 4 + 6 = 10

(5-3)² + 6 = 4 + 6 = 10

Нийт = 20

Оролт-2

2 1000000000000
500000 1000000

Гаралт-2

1250000000000

Оролт-3

8 5
1 3 4 5 10 11 12 13

Гаралт-3

62