Make Swamp Great Again

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

Around the large swamp where Shrek lives, there are \(n\) forest creatures, each living in a house arranged in a circle such that creatures \(i\) and \(i + 1\) live in neighboring houses, and the \(n\)-th creature is also a neighbor of the 1st creature. Each creature has a preferred swamp temperature \(t_i\) in which it feels most comfortable. One day, Shrek decided he wanted all the creatures to experience the same comfort in the swamp by having the same preferred temperature.

Every evening, Shrek invites a few creatures for a meeting. During this meeting, a group of three creatures from consecutive houses is selected, and one of them can change its preferred temperature to either the minimum or the maximum preferred temperature among the three.

For each creature, determine the minimum number of evenings required for Shrek to make all the creatures have the same preferred temperature as the initial temperature of this creature.

Вхідні дані

The first line of the input contains a single integer \(n\) — the number of forest creatures.

The second line contains \(n\) integers \(t_i\) — the preferred temperature of the creature, given in clockwise order around the swamp.

Вихідні дані

Print \(n\) space separated numbers in a single line. The \(i\)-th number represents the minimum number of evenings required to make all preferred temperatures equal to \(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

Примітки

The images below show each evening’s meeting, with groups of three creatures gathering. By the end, all creatures preferred temperature is 4 degrees.