Problem
Satu siri kuliah di Universiti Flatland ditumpukan kepada kajian jujukan.
Profesor memanggil jujukan integer
\(a_1, a_2, ..., a_n\) harmoni jika setiap nombor kecuali
\(a_1\) dan
\(a_n\), sama dengan jumlah bersebelahan:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Contohnya, jujukan [1,2,1,–1] adalah harmonik kerana 2=1+1 dan 1=2+(–1) .
Pertimbangkan urutan yang sama panjang:
\(A=[a_1,a_2, ... a_n]\) dan
\(B=[b_1,b_2, ... b_n]\). Jarak antara jujukan ini akan dipanggil nilai
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Contohnya,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | ++|1–0|+|–1–0|=0+0+1+1=2 \)
Pada akhir kuliah, profesor menulis di papan hitam urutan n integer
\(B=[b_1,b_2, ... b_n]\)dan bertanya pelajar mencari urutan harmoni
\(A=[a_1,a_2, ... a_n]\) supaya
\( d( A, B)\) adalah minimum. Untuk memudahkan dirinya menyemak, profesor meminta anda menulis sebagai jawapan hanya jarak minimum yang dikehendaki
\(d(A,B)\) .
Ia diperlukan untuk menulis atur cara yang, diberi urutan B, menentukan pada jarak minimum dari urutan B terdapat jujukan harmonik A.
Input
Baris pertama fail input mengandungi integer n – bilangan elemen dalam jujukan (
\(3 \le n \le 500\)).
Baris kedua mengandungi n integer
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Cetakan
Fail output mesti mengandungi satu integer: jarak minimum yang mungkin dari jujukan dalam fail input ke jujukan harmonik.
Contoh
| # |
Input |
Output |
| 1 |
4
1 2 0 0
| 2 |