2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Help BerLine

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVery soon, the new cell phone services provider "BerLine" will begin its work in Berland!

The start of customer service is planned along the main street of the capital. There are $$$n$$$ base stations that are already installed. They are located one after another along the main street in the order from the $$$1$$$-st to the $$$n$$$-th from left to right.

Currently, all these base stations are turned off. They will be turned on one by one, one base station per day, according to some permutation $$$p = [p_1, p_2, \dots, p_n]$$$ ($$$ 1 \le p_i \le n$$$), where $$$p_i$$$ is the index of a base station that will be turned on on the $$$i$$$-th day. Thus, it will take $$$n$$$ days to turn on all base stations.

Each base station is characterized by its operating frequency $$$f_i$$$ — an integer between $$$1$$$ and $$$24$$$, inclusive.

There is an important requirement for operating frequencies of base stations. Consider an arbitrary moment in time. For any phone owner, if we consider all base stations turned on in the access area of their phone, then in this set of base stations there should be at least one whose operating frequency is unique among the frequencies of these stations. Since the power of the phone and the position are not known in advance, this means that for any nonempty subsegment of turned on base stations, at least one of them has to have the operating frequency that is unique among the stations of this subsegment.

For example, let's take a look at a case of $$$n = 7$$$, all $$$n$$$ stations are turned on, and their frequencies are equal to $$$f = [1, 2, 1, 3, 1, 2, 1]$$$. Consider any subsegment of the base stations — there is a base station with a unique frequency within this subsegment. However, if $$$f = [1, 2, 1, 2, 3, 2, 1]$$$, then there is no unique frequency on the segment $$$[1, 2, 1, 2]$$$ from the index $$$1$$$ to the index $$$4$$$, inclusive.

Your task is to assign a frequency from $$$1$$$ to $$$24$$$ to each of $$$n$$$ base stations in such a way that the frequency requirement is met at every moment. Remember that the base stations are turned on in the order of the given permutation $$$p$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases in the input. Then $$$t$$$ test case descriptions follow.

The first line of a test case contains an integer $$$n$$$ ($$$ 1 \le n \le 8\,500$$$) — the number of "BerLine" base stations.

The following line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — the order in which the base stations are turned on, i. e. on the $$$i$$$-th day the base station with the index $$$p_i$$$ is turned on.

It is guaranteed that a correct answer exists for all test cases in the input.

Output

Print exactly $$$t$$$ lines, where the $$$j$$$-th line contains the answer for the $$$j$$$-th test case in the input. Print the required frequencies $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_i \le 24$$$). If there are several possible answers, print any of them.

Example

Input

5 3 1 3 2 3 1 2 3 1 1 10 6 10 4 2 7 9 5 8 3 1 10 2 4 6 9 1 8 10 5 3 7

Output

1 3 2 10 20 10 1 2 3 4 5 3 1 3 5 4 2 1 2 3 4 5 6 7 8 9 10

Note

In the first test case $$$n = 3$$$ and $$$p = [1, 3, 2]$$$. The base stations can be assigned frequencies $$$[1, 3, 2]$$$.

- Day 1: only the base station $$$1$$$ is turned on, its frequency is $$$1$$$.
- Day 2: the base stations $$$1$$$ and $$$3$$$ are turned on, their frequencies are $$$[1, 2]$$$.
- Day 3: all base stations are turned on, their frequencies are $$$[1, 3, 2]$$$ (in the direction along the street).

On each day, each nonempty subsegment of turned on base stations has a base station with a unique frequency among this subsegment. It can be shown that three distinct frequencies are necessary in this test case.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2021 22:02:25 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|