Бесі знає число \(x+0.5\), де \(x\) - деяке ціле число між \(0\) і \(N\), включно (\(1\le N\le 2 \cdot 10^5\)).

Ельза намагається вгадати це число. Вона може ставити питання виду "число \(i\) більше чи менше?" для деякого \(i\) між \(1\) і \(N\), включно. Бесі відповідає "HI", якщо число \(i\) більше ніж \(x+0.5\), або "LO" якщо число \(i\) менше, ніж \(x+0.5\).

При вгадуванні числа Ельза слідує наступній стратегії. Спочатку вона створює список із \(N\) чисел, де кожне число від \(1\) до \(N\) зустрічається рівно один раз (іншими словами, цей перелік є перестановка розміру \(N\)). Потім вона йде за цим списком запитуючи число з цього списку.

Але Ельза пропускає марні питання, наприклад, якщо Ельза зараз повинна запитати про число \(i\), а раніше вона запитувала про число \(j < i\) і Бесі відповідала "HI", тоді Ельза не питає про \(i\) і переходить до наступного числу в перестановці. Аналогічно, якщо вона раніше питала про \(j> i\) і отримувала відповідь "LO", Ельза не запитує про \(i\) і переходить до наступного числа в списку. Можна довести, що дотримуюсь такої стратегії, Ельза завжди однозначно визначить \(x\) незалежно від перестановки, яку створить.

Якщо ми конкатенуємо всі відповіді Бесі виду "HI" або "Lo" в один рядок \(S\), тоді кількість разів, коли Бесі сказала "HILO" є кількість підрядків довжини \(4\) у рядку \(S\), які рівні "HILO".

Бесі знає стратегію Ельзи; більше того, вона також знає точну перестановку, яку Ельза використовуватиме. Проте Бесі ще вирішила яке число \(x\) буде використовувати.

Допоможіть Бесі визначити скільки разів вона скаже "HILO" для кожного значення \(x\).

Формат вхідних даних

Перший рядок містить \(N\).

Другий рядок містить перестановку Ельзи розміру \(N\).

Формат вихідних даних

Для кожного \(x\) в інтервалі від \(0\) до \(N\), включно, на окремому рядку виведіть кількість разів яке Бесі скаже "HILO"

Приклад вхідних даних-1

5
5 1 2 4 3

Приклад вихідних даних-1

0
1
1
2
1
0

Пояснення до прикладу-1

Для \(x=0\), Бесі скаже "HIHI" - 0 разів.

Для \(x=2\), Бесі скаже "HILOLOHIHI" - один раз "HILO".

Для \(x=3\), Бесі скаже "HILOLOHILO" - двічі "HILO".

Оцінювання

• У тестах 1-4 \(N \leq 5000\).
• Тести 5 - 8 мають рівномірно випадкову перестановку.
• У тестах 9 - 20 немає додаткових обмежень.