Hello 2024 |
---|
Finished |
You are given an array $$$a$$$ of size $$$n$$$. You will do the following process to calculate your penalty:
If you perform the above process optimally, find the minimum possible penalty you will receive.
$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements.
$$$^\ddagger$$$ Some valid ways to split array $$$a=[3,1,4,1,5]$$$ into $$$(s,t)$$$ are $$$([3,4,1,5],[1])$$$, $$$([1,1],[3,4,5])$$$ and $$$([\,],[3,1,4,1,5])$$$ while some invalid ways to split $$$a$$$ are $$$([3,4,5],[1])$$$, $$$([3,1,4,1],[1,5])$$$ and $$$([1,3,4],[5,1])$$$.
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the size of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output a single integer representing the minimum possible penalty you will receive.
551 2 3 4 588 2 3 1 1 7 4 353 3 3 3 31122 1
3 1 0 0 0
In the first test case, a possible way to split $$$a$$$ is $$$s=[2,4,5]$$$ and $$$t=[1,3]$$$. The penalty is $$$p(s)+p(t)=2 + 1 =3$$$.
In the second test case, a possible way to split $$$a$$$ is $$$s=[8,3,1]$$$ and $$$t=[2,1,7,4,3]$$$. The penalty is $$$p(s)+p(t)=0 + 1 =1$$$.
In the third test case, a possible way to split $$$a$$$ is $$$s=[\,]$$$ and $$$t=[3,3,3,3,3]$$$. The penalty is $$$p(s)+p(t)=0 + 0 =0$$$.
Name |
---|