Пил şəklində yaxınlaşma

Bir ardıcıllıq N tam ədədlərdən ibarət B[0], B[1], ..., B[N-1] mişarvari adlanır, əgər aşağıdakı iki şərt ödənilirsə:

1. Bütün cüt i üçün (0-dan N-2-yə qədər daxil olmaqla), B[i] < B[i+1].

2. Bütün tək i üçün (0-dan N-2-yə qədər daxil olmaqla), B[i] > B[i+1].

Sizə N tam ədədlərdən ibarət A[0], A[1], ..., A[N-1] ardıcıllığı verilib. Bu ardıcıllığı mişarvari ardıcıllıq B[0], B[1], ..., B[N-1] ilə mümkün qədər yaxınlaşdırmaq lazımdır. Yaxınlaşdırma dərəcəsi |B[0] - A[0]| + |B[1] - A[1]| + ... + |B[N-1] - A[N-1]| cəmi ilə ölçülür. Ən yaxşı yaxınlaşdırma, bu cəmin minimal olduğu halda hesab edilir.

Giriş verilənləri

Birinci sətirdə N (3 ≤ N ≤ 100) - massiv ölçüsü verilir. Növbəti N sətirdə verilmiş ardıcıllıq A[0], A[1], ..., A[N-1] (1 ≤ A[i] ≤ 1000000000) təsvir edilir. Bu ardıcıllığın mişarvari yaxınlaşdırmasını tapmaq lazımdır.

Çıxış verilənləri

Tam ədəd olaraq, A[0], A[1], ..., A[N-1] ardıcıllığının mişarvari ardıcıllıq B[0], B[1], ..., B[N-1] vasitəsilə minimal mümkün yaxınlaşdırma dərəcəsinə bərabər olan dəyəri verin.

Nümunələr