Make Swamp Great Again

Limits: 2 sec., 512 MiB

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.

Input

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.

Output

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\).

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
6 4 7 47 4 77 47	4 6 4 4 5 4

Notes

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