Barkley II
本题没有可用的提交语言。
Description
Prof.Hui is the coach of Pigeland University Programming Team. There are $n$ students in his team. All algorithms are numbered by Prof.Hui in ascending order of difficulty, from $1$ to $m$. Which means that algorithm $1$ is the easiest algorithm, while algorithm $m$ is the hardest. The $i$-th student masters the $a_i$-th easiest algorithm.
Now Prof.Hui wants to choose a team satisfying the following conditions:
- The index of the students in the team forms an interval. Which means that there exists two integers $l, r$ such that $1\leq l\leq r\leq n$ and student $x$ is in the team if and only if $l\leq x\leq r$.
- The rating of the team is maximized. The more algorithms the team mastered, the stronger they are, but if they cannot solve a hard problem in one contest, they will feel more disappointed. So the rating of the team is the number of different algorithms that the students in the team mastered minus the index of the easiest algorithm that no one in the team mastered. If the students in the team masters all the algorithms, the index of the easiest algorithm that no student in the team mastered is considered to be $m+1$. For example, if $m=5$ and there are $6$ students in the team, mastering algorithm $2,5,4,4,1,1$ respectively, the rating of the team is $4 - 3 = 1$.
Please help Prof.Hui to find the maximum rating of a team.
The first line contains an integer $t$ ($1\leq t\leq 5\cdot 10^5$), denoting the number of test cases.
For each test case, the first line contains two integer $n, m$ ($1\leq n,m\leq 5\cdot 10^5$), denoting the number of students and the number of algorithms.
The second line contains $n$ integers, the $i$-th integer $a_i$ ($1\leq a_i\leq m$) denoting the number of algorithm the $i$-th student masters.
It is guaranteed that the sum of $n$ over all testcases does not exceed $5\cdot 10^5$. Please notice that there is no limit on sum of $m$.
For each test case, output one integer in one line, denoting the answer.
Input
The first line contains an integer $t$ ($1\leq t\leq 5\cdot 10^5$), denoting the number of test cases.
For each test case, the first line contains two integer $n, m$ ($1\leq n,m\leq 5\cdot 10^5$), denoting the number of students and the number of algorithms.
The second line contains $n$ integers, the $i$-th integer $a_i$ ($1\leq a_i\leq m$) denoting the number of algorithm the $i$-th student masters.
It is guaranteed that the sum of $n$ over all testcases does not exceed $5\cdot 10^5$. Please notice that there is no limit on sum of $m$.
Output
For each test case, output one integer in one line, denoting the answer.
2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1
2
3