Codeforces Round 872 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

implementation

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. LuoTianyi and the Show

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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:

- 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$$$.
- 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$$$.
- 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?

Input

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:

- If $$$x_i=-1$$$, then $$$i$$$-th person takes the seat in the first way.
- If $$$x_i=-2$$$, then $$$i$$$-th person takes the seat in the second way.
- 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$$$.

Output

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

Example

Input

103 105 5 54 61 -2 -2 15 7-1 -1 4 -2 -26 75 -2 -2 -2 -2 -26 6-1 1 4 5 -1 46 8-1 -1 -1 3 -1 -26 75 -1 -2 -2 -2 -23 1-2 -2 12 55 -21 2-1

Output

1 3 5 6 5 5 5 1 2 1

Note

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:

– | – | – | 3 | 4 | – | – |

Let the fifth person in:

– | – | – | 3 | 4 | 5 | – |

Let the first person in:

– | – | 1 | 3 | 4 | 5 | – |

Let the second person in:

– | 2 | 1 | 3 | 4 | 5 | – |

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:

– | – | – | 3 | 4 | – |

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:

– | – | – | 3 | 4 | – |

Let the fifth person in:

– | – | 5 | 3 | 4 | – |

Let the first person in:

– | 1 | 5 | 3 | 4 | – |

Let the second person in:

2 | 1 | 5 | 3 | 4 | – |

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:

3 | 4 | – | – | – | – | – |

Let the fifth person in:

3 | 4 | 5 | – | – | – | – |

Let the sixth person in:

3 | 4 | 5 | 6 | – | – | – |

Let the first person in:

3 | 4 | 5 | 6 | 1 | – | – |

Let the second person in, he will leave the show because he occupies the first way, but the $$$1$$$ seat is taken:

3 | 4 | 5 | 6 | 1 | – | – |

Thus, $$$5$$$ people took seats.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:28:03 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|