Мова Вестероса#12425

Мова Вестероса

1 секунда

256 мегабайтів

Дуже складна

Лазаючи вежами Вінтерфелла, Бран Старк натрапив на масив,що складається з $n$ вестероських букв. Як відомо, Вестероський алфавіт складається з $m$ розташованих по колу букв, кожна з яких характеризується цілим числом $a_{i}$ a_i.

Подивившись на масив, Бран вирішив перетворити його на паліндром, попередньо перемішавши букви в довільному порядку. За одну операцію він може замінити довільну букву масиву на наступну букву в алфавіті за годинниковою або проти годинникової стрілки. Коли він замінює довільну букву $i$ на наступну за годинниковою стрілкою, вона переходить у букву $i + 1$ i+1,а буква $m$ переходить у $1$ . Аналогічно, замінюючи букву $i$ на наступну проти годинникової стрілки, вона переходить у букву $i - 1$ i-1, а буква $1$ переходить у $m$ .

Леді Кетлін Старк вже вирушила на пошуки свого сина, тому Бран прагне досягти мети за найменшу можливу кількість операцій, і він просить вас сказати йому цю кількість.

Вхідні дані

Перший рядок містить ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків. Опис тестових випадків слідує далі.

Перший рядок кожного тестового випадку містить два цілих числа $n$ та $m$ ( $1 \leq n \leq 4 \cdot 1 0^{5}$ 1 \le n \le 4 \cdot 10^5, $1 \leq m \leq 2 \cdot 1 0^{5}$ 1 \le m \le 2 \cdot 10^5) — довжина масиву та кількість букв в алфавіті.

Наступний рядок містить масив цілих чисел $a$ довжиною $n$ ( $1 \leq a_{i} \leq m$ 1 \le a_i \le m) — масив на який натрапив Бран Старк.

Гарантується, що сума $n$ по всім тестовим випадкам не перевищує $4 \cdot 1 0^{5}$ 4 \cdot 10^5

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Примітка

Пояснення до першого набору тестів

В першому прикладі спершу можна перемішати букви в порядку $[2, 4, 6, 9, 7, 5, 2]$ [2,4,6,9,7,5,2], посунути другу букву за годинниковою стрілкою і пʼяту проти годинникової стрілки, в результаті отримавши масив $[2, 5, 6, 9, 6, 5, 2]$ [2,5,6,9,6,5,2], який є паліндромом.

В другому прикладі, перемішавши спочатку букви в порядку $[1, 3, 2, 1, 1, 3, 3, 1]$ [1,3,2,1,1,3,3,1], а потім посунувши третю букву за годинниковою стрілкою, отримаємо масив $[1, 3, 3, 1, 1, 3, 3, 1]$ [1,3,3,1,1,3,3,1], який є паліндромом.

Оцінювання

Підзадача $1$ ( $25$ балів) : $(n \leq 10)$ (n\le 10)
Підзадача $2$ ( $35$ балів) : $(m \leq 2)$ (m \le 2)
Підзадача $3$ ( $50$ балів) : ( $n$ — парне)
Підзадача $4$ ( $60$ балів) : $(n \leq 100)$ (n \le 100)
Підзадача $5$ ( $130$ балів) : Без додаткових обмежень