HILO (Золото)

Бесі знає число x + 0.5, де $x$ — це деяке ціле число від $0$ до $n$, включно.

Ельза намагається вгадати це число. Вона може ставити запитання типу "чи більше число $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$.