Никита очень любит задачи на порядковую статистику. В частности, он легко сможет найти \(k\)-е в порядке возрастания число на отрезке массива. Однако сейчас он задумался: а сколько существует отрезков данного массива таких, что данное число \(x\) — \(k\)-е по возрастанию на данном отрезке? Иными словами, вам нужно посчитать количество подотрезков данного массива, содержащих ровно \(k\) чисел, меньших чем \(x\).
Никиту интересует ответ на данный вопрос для всех \(k\) от \(0\) до \(n\), где \(n\) — длина массива.
Выходные данные
Выведите \(n+1\) число, где \(i\)-е число — ответ на вопрос Никиты для \(k=i-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 2 3 4 5
|
6 5 4 0 0 0
|
|
2
|
2 6
-5 9
|
1 2 0
|
|
3
|
6 99
-1 -1 -1 -1 -1 -1
|
0 6 5 4 3 2 1
|