Do You Know LIS?

ashikurrahman AUST Programming Lab 2 Se...
Limits 3s, 512 MB

Alam has an array aa with nn elements a1,a2,,ana_1, a_2, …, a_n and an integer xx.

For each ii (1in1)(1 \le i \le n - 1) index ii and i+1i + 1 are neighbours. But recently index xx had a quarrel with his neighbour x+1x + 1. So they are not neighbour anymore.

Alam loves Longest Increasing subsequences and wants the Longest Increasing subsequence of the array aa to be as long as possible.

You have a special power. You can swap any two values of the array aa if they are neighbors.

So, help Alam find his Longest increasing subsequence of the array aa using your special power zero or more number of times.

Input

First line contains a single integer tt (1t105)(1 \le t \le 10^5) the number of test cases.

Each test case starts with two integers nn and xx (2n105)(2 \le n \le 10^5) and (1xn1)(1 \le x \le n - 1) the number of element of the array aa and the integer xx describe in the problem statement.

Next line contains nn space separated integers a1,a2,,ana_1, a_2, …, a_n the elements of the array.

It is guaranteed that the sum of all nn in over all test cases will not exceed 10610^6 and all the elements of array aa will fit into a 32 bit signed integer.

Output

For each test case print a single integer the length of the longest increasing subsequence of the array aa after using you special power zero or more amount of times.

Sample

InputOutput
2
3 1
1 2 3
4 2
2 2 5 4
3
4

Submit

Login to submit.

Statistics

69% Solution Ratio
MatrixEarliest, 1M ago
prodip_bsmrstuFastest, 0.1s
MehrajShakilLightest, 594 kB
obaydullahmhsShortest, 571B
Toph uses cookies. By continuing you agree to our Cookie Policy.