CF1824A LuoTianyi and the Show

There are $ n $ people taking part in a show about VOCALOID. They will sit in the row of seats, numbered $ 1 $ to $ m $ from left to right. The $ n $ people come and sit in order. Each person occupies a seat in one of three ways: 1. Sit in the seat next to the left of the leftmost person who is already sitting, or if seat $ 1 $ is taken, then leave the show. If there is no one currently sitting, sit in seat $ m $ . 2. Sit in the seat next to the right of the rightmost person who is already sitting, or if seat $ m $ is taken, then leave the show. If there is no one currently sitting, sit in seat $ 1 $ . 3. Sit in the seat numbered $ x_i $ . If this seat is taken, then leave the show. Now you want to know what is the maximum number of people that can take a seat, if you can let people into the show in any order?

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^5 $ ) — the number of people and the number of seats. The second line of each test case contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ -2 \le x_i \le m $ , $ x_i \ne 0 $ ), the $ i $ -th of which describes the way in which the $ i $ -th person occupies a seat: 1. If $ x_i=-1 $ , then $ i $ -th person takes the seat in the first way. 2. If $ x_i=-2 $ , then $ i $ -th person takes the seat in the second way. 3. If $ x_i > 0 $ , then the $ i $ -th person takes a seat in the third way, i.e. he wants to sit in the seat with the number $ x_i $ or leave the show if it is occupied.. It is guaranteed that sum of $ n $ and the sum of $ m $ over all test cases don't exceed $ 10^5 $ .

For each test case output a single integer — the maximum number of people who can occupy a seat.

In the first test case, all the people want to occupy the $ 5 $ seat, so only $ 1 $ people can occupy the seat. In the second test case, we can let people in order $ 1, 2, 3, 4 $ , then all but the last person can take a seat. In the third test case, we can let people into the show in that order: Let the third person in: –––3–––Let the fourth person in: –––34––Let the fifth person in: –––345–Let the first person in: ––1345–Let the second person in: –21345–Thus, all $ 5 $ people took seats. In the fifth test case, we can let people into the show in this order: Let the fourth person in: ––––4–Let the third person in: –––34–Let the sixth person in, he'll leave the show because he takes the third seat the third way and has to sit in the $ 4 $ seat, but it's already taken: –––34–Let the fifth person in: ––534–Let the first person in: –1534–Let the second person in: 21534–Thus, $ 5 $ of people took seats. In the seventh test case, we can let people into the show in this order: Let the third person in: 3––––––Let the fourth person in: 34–––––Let the fifth person in: 345––––Let the sixth person in: 3456–––Let the first person in: 34561––Let the second person in, he will leave the show because he occupies the first way, but the $ 1 $ seat is taken: 34561––Thus, $ 5 $ people took seats.