Breaking the Partition - Repovive Premier Round 8 | Repovive

24G. Breaking the Partition

3250 pts3s256 MB

You are given a permutation $p_1, p_2, \ldots, p_n$ .

An array $a_1, a_2, \ldots, a_m$ is called good if its indices can be partitioned into groups such that every group consists of indices $i_1 < i_2 < \cdots < i_k$ , where $k \ge 2$ , and $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$ .

Every index must belong to exactly one group. The indices in a group do not have to be consecutive. The empty array is considered good.

Find the minimum number of elements you must delete from $p$ so that the remaining array is not good. Deleting elements does not change the relative order of the remaining elements.

If $p$ is already not good, the answer is $0$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 5000$
$p$ is a permutation of $1, 2, \ldots, n$ .
The sum of $n$ over all test cases is at most $5000$ .

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

6
2 1 4 3 6 5

Case 2

5
1 2 3 4 5

Explanation

Case 1

Delete the elements at positions 4, 5, and 6. The remaining array is [2, 1, 4]. Its three elements would have to form a single group, but they are not increasing.

Fewer deletions do not suffice. Think of the original positions as three pairs: (1, 2), (3, 4), and (5, 6). Elements chosen from different pairs are increasing in their original order. Any four remaining elements can be split into two groups of two, each using different pairs. Any five remaining elements can be split into a group of three and a group of two. All six elements can be split into [2, 4, 6] and [1, 3, 5].

Case 2

Delete any four elements, leaving a single element, which cannot belong to an allowed group. With fewer deletions, the remaining array is increasing and has length 2, 3, 4, or 5; these lengths can be grouped as 2, 3, 2 + 2, or 2 + 3, respectively.

Output

Case 1

Case 2

Input

Case 1

1
1

Case 2

4
3 2 1 4

Case 3

4
1 2 4 3

Explanation

Case 1

The array contains only one element, so it is already not good.

Case 2

The elements 3, 2, and 1 cannot share a group with one another. Each would need the element 4 in its group, which is impossible because every element belongs to exactly one group. No deletions are needed.

Case 3

Initially, the array can be partitioned into the increasing subsequences [1, 4] and [2, 3]. Delete the element at position 1 to obtain [2, 4, 3]. These three elements are not increasing, so the remaining array is not good.

Output

Case 1

Case 2

Case 3

You are given a permutation $p_1, p_2, \ldots, p_n$ .

Every index must belong to exactly one group. The indices in a group do not have to be consecutive. The empty array is considered good.

Find the minimum number of elements you must delete from $p$ so that the remaining array is not good. Deleting elements does not change the relative order of the remaining elements.

If $p$ is already not good, the answer is $0$ .

$1 \le t \le 100$
$1 \le n \le 5000$
$p$ is a permutation of $1, 2, \ldots, n$ .
The sum of $n$ over all test cases is at most $5000$ .

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24G. Breaking the Partition

Constraints

Input

Output

Samples

24G. Breaking the Partition

Constraints

Input

Output

Samples