E. Изысканный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём массив из чисел $$$k$$$-изысканным, если в нём есть хотя бы два элемента и любые два соседних числа различаются не меньше, чем на $$$k$$$.

Вам даётся перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. Для каждого $$$k$$$ от $$$1$$$ до $$$n - 1$$$ найдите количество $$$k$$$-изысканных подотрезков$$$^{\text{†}}$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, который содержит каждое целое число от $$$1$$$ до $$$n$$$ ровно один раз, в любом порядке.

$$$^{\text{†}}$$$Подотрезок массива — это последовательность из одного или более подряд идущих элементов массива.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 25000)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных даётся целое число $$$n$$$ — длина перестановки $$$(2 \le n \le 10^5)$$$.

Во второй строке каждого набора входных данных даётся $$$n$$$ целых чисел $$$p_i$$$ — элементы перестановки $$$(1 \le p_i \le n)$$$. Гарантируется, что $$$p_i$$$ не повторяются.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите количество $$$k$$$-изысканных подотрезков для всех $$$k$$$ от $$$1$$$ до $$$n - 1$$$.

Пример
Входные данные
3
5
5 1 4 2 3
3
3 2 1
4
3 1 2 4
Выходные данные
10 6 3 1 
3 0 
6 2 0