Беси знает число \(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\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит перестановку Эльзы размера \(N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого \(x\) в интервале от \(0\) до \(N\), включительно, на отдельной строке
выведите количество раз которое Беси скажет "HILO"
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 1 2 4 3
|
0
1
1
2
1
0
|