CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)C

C. Colorful Table

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two integers n� and k�. You are also given an array of integers a1,a2,…,an�1,�2,…,�� of size n�. It is known that for all 1≤i≤n1≤�≤�, 1≤ai≤k1≤��≤�.

Define a two-dimensional array b� of size n×n�×� as follows: bi,j=min(ai,aj)��,�=min(��,��). Represent array b� as a square, where the upper left cell is b1,1�1,1, rows are numbered from top to bottom from 11 to n�, and columns are numbered from left to right from 11 to n�. Let the color of a cell be the number written in it (for a cell with coordinates (i,j)(�,�), this is bi,j��,�).

For each color from 11 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.

Input

The first line contains a single integer t� (1≤t≤1041≤�≤104) — 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≤n,k≤1051≤�,�≤105) — the size of array a� and the number of colors.

The second line of each test case contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤k1≤��≤�) — the array a�.

It is guaranteed that the sum of the values of n� and k� over all test cases does not exceed 105105.

Output

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 11 to k�.

Example

input

Copy

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

output

Copy

Note

In the first test case, the entire array b� consists of color 11, so the smallest rectangle for color 11 has a size of 2×22×2, and the sum of its sides is 44.

In the second test case, the array b� looks like this:

1	1
1	2

One of the corner cells has color 22, and the other three cells have color 11. Therefore, the smallest rectangle for color 11 has a size of 2×22×2, and for color 22 it is 1×11×1.

In the last test case, the array b� looks like this:

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

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
ll LEFT_l[1000010], RIGHT_l[1000010],LEFT_r[1000010], RIGHT_r[1000010];
void findRectangles(ll n, ll k, vector<ll> &a)
{
    for(int i=0; i<max(k,n)+100; i++)
    {
        LEFT_l[i]=1000000;
//        MIN[i]=1000000;
        RIGHT_r[i]=-1;
//        MAX[i]=-1;
    }
    ll MAX=-1,MIN=1000000;
    for (ll i = 0; i < n; i++)
    {
        ll x=a[i];
        LEFT_l[x] = min(LEFT_l[x], i);
        RIGHT_r[x] = max(RIGHT_r[x], i);
    }
    vector<ll>ans;
    ans.clear();
    for(ll i=k; i>0; i--)
    {
        if(LEFT_l[i]==1000000&&RIGHT_r[i]==-1)
        {
            ans.push_back(0);
        }
        else
        {

            MAX=max(MAX,RIGHT_r[i]);
            MIN=min(MIN,LEFT_l[i]);
            ans.push_back(2*(MAX-MIN+1));
        }
    }

    for(int i=0; i<max(n,k)+100; i++)
    {
        LEFT_l[i]=1000000;
//        MIN[i]=1000000;
        RIGHT_r[i]=-1;
//        MAX[i]=-1;
    }

    for (ll i = k-1; i >=0; i--)
    {
        cout<<ans[i]<<' ';
    }
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;

        vector<ll> a(n);
        for (ll i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        findRectangles(n, k, a);
    }

    return 0;
}

清空数组没有清空完全

for(int i=0; i<max(k,n)+100; i++)文章来源地址https://uudwc.com/A/V6zkp

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)C - Colorful Table