Олимпиадный тренинг

Задача . C. Разноцветная таблица


Вам даны два целых числа \(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\).

Примечание

В первом наборе входных данных весь массив \(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


Примеры
№Входные данныеВыходные данные
1
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
Статистика успешных решений по компиляторам
 Кол-во
С++3