A16240 | Colorful Table

You are given two integers $n$ and $k$ . You are also given an array of integers $a_1, a_2, \ldots, a_n$ of size $n$ . It is known that for all $1 \leq i \leq n$ , $1 \leq a_i \leq k$ .

Define a two-dimensional array $b$ of size $n \times n$ as follows: $b_{i, j} = \min(a_i, a_j)$ . Represent array $b$ as a square, where the upper left cell is $b_{1, 1}$ , rows are numbered from top to bottom from $1$ to $n$ , and columns are numbered from left to right from $1$ to $n$ . Let the color of a cell be the number written in it (for a cell with coordinates $(i, j)$ , this is $b_{i, j}$ ).

For each color from $1$ to $k$ , find the smallest rectangle in the array $b$ containing all cells of this color. Output the sum of width and height of this rectangle.

The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $n$ and $k$ ( $1 \leq n, k \leq 10^5$ ) — the size of array $a$ and the number of colors.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq k$ ) — the array $a$ .

It is guaranteed that the sum of the values of $n$ and $k$ over all test cases does not exceed $10^5$ .

For each test case, output $k$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $1$ to $k$ .