Олимпиадный тренинг

Задача . A. LuoTianyi и шоу

Задача

В шоу о VOCALOID принимают участие \(n\) человек. Они будут сидеть в ряду с сиденьями, пронумерованными от \(1\) до \(m\) слева направо.

Все \(n\) людей приходят и садятся по порядку. Каждый человек занимает место одним из трёх способов:

Сесть на соседнее слева место от самого левого человека, который уже сидит, или, если место \(1\) занятно, то покинуть шоу. Если сейчас никто не сидит, то занять место с номером \(m\).
Сесть на соседнее справа место от самого правого человека, который уже сидит, или, если место \(m\) занятно, то покинуть шоу. Если сейчас никто не сидит, то занять место с номером \(1\).
Сесть на место с номером \(x_i\). Если это место занято, то покинуть шоу.

Теперь вы хотите узнать, каково максимальное количество тех, кто может занять место, если вы можете впустить людей на шоу в любом порядке?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)) — количество людей и количество мест.

Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(x_1, x_2, \ldots, x_n\) (\(-2 \le x_i \le m\), \(x_i \ne 0\)), \(i\)-е из которых описывает способ, как \(i\)-й человек занимает место:

Если \(x_i=-1\), то \(i\)-й человек занимает место первым способом.
Если \(x_i=-2\), то \(i\)-й человек занимает место вторым способом.
Если \(x_i > 0\), то \(i\)-й человек занимает место третьим способом, т.е. хочет сесть на место с номером \(x_i\) или покинуть шоу, если оно занято.

Гарантируется, что сумма \(n\) и сумма \(m\) по всем наборам входных данных не превосходят \(10^5\).

Выходные данные

Для каждого набора входных данных выведите единственное целое число — максимальное количество человек, которые могут занять место.

Примечание

В первом наборе входных данных все люди хотят занять место \(5\), поэтому только \(1\) человек сможет занять место.

Во втором наборе входных данных людей можно впустить в порядке \(1, 2, 3, 4\), тогда все люди, кроме последнего, смогут занять место.

В третьем наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим третьего человека:

–

Впустим четвёртого человека:

–

Впустим пятого человека:

–

Впустим первого человека:

–

Впустим второго человека:

–

Таким образом, все \(5\) человек заняли места.

В пятом наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим четвёртого человека:

–

Впустим третьего человека:

–

Впустим шестого человека, он покинет шоу, потому что занимает место третьим способом и должен сесть на место \(4\), но оно уже занято:

–

Впустим пятого человека:

–

Впустим первого человека:

–

Впустим второго человека:

–

Таким образом, \(5\) человек заняли места.

В седьмом наборе входных данных мы можем впускать людей на шоу в таком порядке:

Впустим третьего человека:

–

Впустим четвёртого человека:

–

Впустим пятого человека:

–

Впустим шестого человека:

–

Впустим первого человека:

–

Впустим второго человека, он покинет шоу, потому что занимает место первым способом, но место \(1\) занято:

–

Таким образом, \(5\) человек заняли места.

Примеры

№	Входные данные	Выходные данные
1	10 3 10 5 5 5 4 6 1 -2 -2 1 5 7 -1 -1 4 -2 -2 6 7 5 -2 -2 -2 -2 -2 6 6 -1 1 4 5 -1 4 6 8 -1 -1 -1 3 -1 -2 6 7 5 -1 -2 -2 -2 -2 3 1 -2 -2 1 2 5 5 -2 1 2 -1	1 3 5 6 5 5 5 1 2 1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет