Вам даны два целых числа \(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\), содержащий все клетки этого цвета. Выведите сумму ширины и высоты этого прямоугольника.
Выходные данные
На каждый набор входных данных выведите \(k\) чисел: сумму ширины и высоты минимального прямоугольника, содержащего все клетки одного цвета, для цветов от \(1\) до \(k\).
Примечание
В первом наборе входных данных весь массив \(b\) состоит из цвета \(1\), поэтому минимальный прямоугольник для цвета \(1\) имеет размер \(2 \times 2\), сумма его сторон это \(4\).
Во втором наборе входных данных массив \(b\) выглядит так:
Одна из угловых клеток имеет цвет \(2\), три остальные клетки имеют цвет \(1\). Поэтому для цвета \(1\) минимальный прямоугольник имеет размер \(2 \times 2\), а для цвета \(2\) — \(1 \times 1\).
В последнем наборе входных данных \(b\) выглядит так:
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 1 |
| 1 | 2 | 3 | 2 | 1 |
| 1 | 2 | 2 | 2 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Примеры
| № | Входные данные | Выходные данные |
|
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
|