题目描述

Very 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$.

输入格式

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.

输出格式

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.

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

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

提示

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.