C. Разноцветная таблица
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$n$$$ и $$$k$$$. Также вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ размера $$$n$$$. Известно, что для всех $$$1 \leq i \leq n$$$ верно, что $$$1 \leq a_i \leq k$$$.

Определим двумерный массив $$$b$$$ размера $$$n \times n$$$ так: $$$b_{i, j} = \min(a_i, a_j)$$$. Представим массив $$$b$$$ как квадрат, где верхняя левая клетка — это $$$b_{1, 1}$$$, строки нумеруются сверху вниз от $$$1$$$ до $$$n$$$, столбцы — слева направо от $$$1$$$ до $$$n$$$. Назовём цветом клетки число, которое в ней записано (для клетки с координатами $$$(i, j)$$$ это $$$b_{i, j}$$$).

Для каждого цвета от $$$1$$$ до $$$k$$$ найдём минимальный прямоугольник в массиве $$$b$$$, содержащий все клетки этого цвета. Выведите сумму ширины и высоты этого прямоугольника.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) — размер массива $$$a$$$, а также количество цветов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$) — массив $$$a$$$.

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

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

На каждый набор входных данных выведите $$$k$$$ чисел: сумму ширины и высоты минимального прямоугольника, содержащего все клетки одного цвета, для цветов от $$$1$$$ до $$$k$$$.

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

В первом наборе входных данных весь массив $$$b$$$ состоит из цвета $$$1$$$, поэтому минимальный прямоугольник для цвета $$$1$$$ имеет размер $$$2 \times 2$$$, сумма его сторон это $$$4$$$.

Во втором наборе входных данных массив $$$b$$$ выглядит так:

11
12

Одна из угловых клеток имеет цвет $$$2$$$, три остальные клетки имеют цвет $$$1$$$. Поэтому для цвета $$$1$$$ минимальный прямоугольник имеет размер $$$2 \times 2$$$, а для цвета $$$2$$$ — $$$1 \times 1$$$.

В последнем наборе входных данных $$$b$$$ выглядит так:

11111
12221
12321
12221
11111