Беси знает число 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.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 2 * 105).

Вторая строка содержит перестановку Эльзы размера n.

Выходные данные

Для каждого x в интервале от 0 до n, включительно, на отдельной строке выведите количество раз которое Беси скажет "HILO".

Пример

Для x = 0, Беси скажет "HIHI" - 0 раз.

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

Для x = 3, Беси скажет "HILOLOHILO" - два раза "HILO".