Вам задан массив \(a\), состоящий из \(n\) целых чисел (гарантируется, что \(n\) четное, то есть делится на \(2\)). Все \(a_i\) не превосходят некоторое число \(k\).
Ваша задача — заменить минимальное количество элементов (под заменой понимается следующая операция: выбрать некоторый индекс \(i\) от \(1\) до \(n\) и заменить \(a_i\) на некоторое целое число в отрезке \([1; k]\)) так, чтобы удовлетворялись следующие условия:
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Первая строка теста содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов тестовых данных. Затем следуют \(t\) наборов тестовых данных.
Первая строка набора тестовых данных содержит два целых числа \(n\) и \(k\) (\(2 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5\)) — длину \(a\) и максимально возможное значение \(a_i\) соответственно. Гарантируется, что \(n\) четное (то есть делится на \(2\)). Вторая строка набора содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le k\)), где \(a_i\) — \(i\)-й элемент в \(a\).
Гарантируется, что сумма чисел \(n\) (так же, как и сумма чисел \(k\)) по всем наборам тестовых данных не превосходит \(2 \cdot 10^5\) (\(\sum n \le 2 \cdot 10^5\), \(\sum k \le 2 \cdot 10^5\)).
Для каждого набора тестовых данных выведите в ответ на него — минимальное количество элементов, которое нужно заменить в \(a\), чтобы удовлетворить все условия задачи.
4 4 2 1 2 1 2 4 3 1 2 2 1 8 7 6 1 1 7 6 3 4 6 6 6 5 2 6 1 3 4
0 1 4 2
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач