Условие:
В ваш первый рабочий день на стажировке решили провести тимбилдинг внутри команды. Всех $n$ людей в команде расставили по кругу, а также $i$-му человеку в круге выдали бумажку с числом $a_i$. Затем происходит игра:
Каждый раз выбираются $3$ подряд идущих человека. Они сдают свои бумажки. После чего у одного из них могут изменить число, записанное на бумажке, либо на максимальное число среди сданных, либо же на минимальное. После чего им обратно отдают свои бумажки. Игра заканчивается, когда у всех людей будет записано одно и тоже число на бумажке.
Команда не хочет в это играть, поэтому требуется ответить на следующий вопрос — для каждого человека требуется сообщить, какое минимальное количество раз придется сдавать бумажки, чтобы в конце игры на всех бумажках было записано одинаковое число, равное числу, записанному изначально у данного человека.
Входные данные
В первой строке задано число $n$ ($3 \le n \le 10^5$) — количество людей в команде.
Во второй строке записано $n$ чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — изначальные числа на бумажках у команды.
Выходные данные
Выведите $n$ чисел — ответ на задачу для $i$ человека.
Примеры данных
Пример 1
3
1 2 3
3
2 3 2
Пример 2
4
1 2 1 3
2 3 2 3
