Навколо великого болота, де живе Шрек, є лісових створінь, кожне з яких мешкає в будинку. Будинки розташовані по колу, так що створіння та i + 1 живуть у сусідніх будинках, а -те створіння є сусідом першого створіння. Кожне створіння має улюблену температуру болота t_i, за якої воно почувається найбільш комфортно. Одного дня Шрек вирішив, що хоче, щоб усі створіння відчували однаковий комфорт у болоті, тобто щоб усі вони мали однакову улюблену температуру.
Щовечора Шрек запрошує кількох створінь на зустріч. Під час цієї зустрічі обирається група з трьох створінь, що живуть у трьох сусідніх будинках, і одне з них може змінити свою улюблену температуру на мінімальне або максимальне значення серед температур цієї трійки.
Для кожного створіння визначте мінімальну кількість вечорів, потрібну Шреку, щоб зробити всі улюблені температури створінь однаковими з початковою температурою цього створіння.
У першому рядку задано одне ціле число — кількість лісових створінь.
У другому рядку задано цілих чисел t_i — початкова улюблена температура -того створіння, задані в порядку за годинниковою стрілкою довкола болота.
3 \le n \le 10^5,
1 \le t_i \le 10^5.
В одному рядку виведіть цілих чисел, розділених пробілом. -те число позначає мінімальну кількість вечорів потрібну, щоб зробити улюблену температуру всіх створінь рівною t_i.
Приклад
Ці картинки показують вечірні зустрічі, де групи по три створіння збираються разом. В кінці, улюблена температура всіх створінь є рівною 4.