Codeforces Round 954 (Div. 3) |
---|
Закончено |
Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$. Вам нужно сделать его красивым за наименьшее количество операций.
До применения операций вы можете перемешать элементы массива как угодно. За одну операцию вы можете сделать следующее:
Массив $$$b_1, b_2, \ldots, b_n$$$ является красивым, если $$$b_i = b_{n - i + 1}$$$ для всех $$$1 \leq i \leq n$$$.
Найдите наименьшее количество операций, за которое можно сделать массив красивым, или сообщите, что это невозможно.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) — размер массива $$$a$$$ и число $$$k$$$ из условия задачи.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы массив стал красивым, или $$$-1$$$, если это невозможно.
111 100000000012 1624323799 7082903233 13 2 14 17 1 5 35 111 2 15 7 107 11 8 2 16 8 16 3113 12 1 1 3 3 11 12 22 45 777 777 1500 7410 21 2 1 2 1 2 1 2 1 211 21 2 1 2 1 2 1 2 1 2 113 32 3 9 14 17 10 22 20 18 30 1 4 285 12 3 5 3 5
0 83966524 1 4 6 1 48 -1 0 14 0
В первом наборе входных данных массив уже является красивым.
Во втором наборе входных данных можно не перемешивать массив до операций и $$$83966524$$$ раз сделать операцию с индексом $$$i = 1$$$.
В третьем наборе входных данных можно перемешать массив $$$a$$$ и сделать его равным $$$[2, 3, 1]$$$. После этого применить операцию с индексом $$$i = 3$$$, чтобы получился массив $$$[2, 3, 2]$$$, который является красивым.
В восьмом наборе входных данных не существует набора операций и способа перемешать элементы, чтобы сделать массив красивым.
В девятом наборе входных данных массив уже является красивым.
Название |
---|