Зробимо болото великим знову!

Обмеження: 2 сек., 512 МіБ

Навколо великого болота, де живе Шрек, є \(n\) лісових створінь, кожне з яких мешкає в будинку. Будинки розташовані по колу, так що створіння \(i\) та \(i + 1\) живуть у сусідніх будинках, а \(n\)-те створіння є сусідом першого створіння. Кожне створіння має улюблену температуру болота \(t_i\), за якої воно почувається найбільш комфортно. Одного дня Шрек вирішив, що хоче, щоб усі створіння відчували однаковий комфорт у болоті, тобто щоб усі вони мали однакову улюблену температуру.

Щовечора Шрек запрошує кількох створінь на зустріч. Під час цієї зустрічі обирається група з трьох створінь, що живуть у трьох сусідніх будинках, і одне з них може змінити свою улюблену температуру на мінімальне або максимальне значення серед температур цієї трійки.

Для кожного створіння визначте мінімальну кількість вечорів, потрібну Шреку, щоб зробити всі улюблені температури створінь однаковими з початковою температурою цього створіння.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість лісових створінь.

У другому рядку задано \(n\) цілих чисел \(t_i\) — початкова улюблена температура \(i\)-того створіння, задані в порядку за годинниковою стрілкою довкола болота.

Вихідні дані

В одному рядку виведіть \(n\) цілих чисел, розділених пробілом. \(i\)-те число позначає мінімальну кількість вечорів потрібну, щоб зробити улюблену температуру всіх створінь рівною \(t_i\).

Обмеження

\(3 \le n \le 10^5\),

\(1 \le t_i \le 10^5\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 4 7 47 4 77 47	4 6 4 4 5 4

Примітки

Ці картинки показують вечірні зустрічі, де групи по три створіння збираються разом. В кінці, улюблена температура всіх створінь є рівною 4.