Vesterosun Dili#12425

Vesterosun Dili

1 saniyə

256 meqabayt

Çox çətin

Winterfell qüllələrinə dırmaşarkən, Bran Stark $n$ ədəd Vesteros hərfindən ibarət bir massivə rast gəldi. Məlum olduğu kimi, Vesteros əlifbası dairə şəklində düzülmüş $m$ hərfdən ibarətdir və hər biri $a_{i}$ a_i tam ədədi ilə xarakterizə olunur.

Massivə baxan Bran, əvvəlcə hərfləri istənilən qaydada qarışdırdıqdan sonra onu palindroma çevirməyə qərar verdi. Bir əməliyyatda o, massivdəki istənilən hərfi əlifbada saat istiqamətində və ya saat əksinə növbəti hərflə əvəz edə bilər. Əgər o, $i$ hərfini saat istiqamətində növbəti hərflə əvəz edərsə, o, $i + 1$ i+1 hərfinə çevrilir, və $m$ hərfi $1$ olur. Eynilə, əgər o, $i$ hərfini saat əksinə növbəti hərflə əvəz edərsə, o, $i - 1$ i-1 hərfinə çevrilir, və $1$ hərfi $m$ olur.

Lady Catelyn Stark artıq oğlunu axtarmağa çıxıb, buna görə Bran bu məqsədə mümkün olan ən az əməliyyatla çatmaq istəyir və sizdən bu ədədi deməyinizi xahiş edir.

Giriş

Birinci sətirdə $t$ tam ədədi verilir $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test nümunələrinin sayı. Test nümunələrinin təsviri ardınca verilir.

Hər test nümunəsinin birinci sətrində iki tam ədəd $n$ və $m$ verilir $(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) — massivin uzunluğu və əlifbadakı hərflərin sayı.

Növbəti sətirdə uzunluğu $n$ olan $a$ tam ədədlər massivi verilir $(1 \leq a_{i} \leq m)$ (1 \le a_i \le m) — Bran Starkın rast gəldiyi massiv.

Bütün test nümunələri üzrə $n$ -lərin cəminin $4 \cdot 1 0^{5}$ 4 \cdot 10^5-i aşmadığı təmin olunur.

Çıxış

Hər sorğu üçün bir ədəd çıxarın — təsvir olunan əməliyyatların minimum sayını, massivi palindroma çevirmək üçün.

Nümunələr

Nümunə 1

Nümunə 2

Qeyd

Birinci test nümunəsi üçün izah

Birinci nümunədə əvvəlcə hərfləri $[2, 4, 6, 9, 7, 5, 2]$ [2,4,6,9,7,5,2] sırasına qarışdırmaq, sonra ikinci hərfi saat istiqamətində və beşinci hərfi saat əksinə hərəkət etdirmək olar; nəticədə $[2, 5, 6, 9, 6, 5, 2]$ [2,5,6,9,6,5,2] massivi alınır ki, bu da palindromdur.

İkinci nümunədə əvvəlcə hərfləri $[1, 3, 2, 1, 1, 3, 3, 1]$ [1,3,2,1,1,3,3,1] sırasına qarışdırdıqdan sonra üçüncü hərfi saat istiqamətində hərəkət etdirməklə $[1, 3, 3, 1, 1, 3, 3, 1]$ [1,3,3,1,1,3,3,1] massivini alırıq ki, bu da palindromdur.

Bal hesablama

Alt tapşırıq $1$ ( $25$ xal): $(n \leq 10)$ (n\le 10)
Alt tapşırıq $2$ ( $35$ xal): $(m \leq 2)$ (m \le 2)
Alt tapşırıq $3$ ( $50$ xal): $(n$ — cütdür)
Alt tapşırıq $4$ ( $60$ xal): $(n \leq 100)$ (n \le 100)
Alt tapşırıq $5$ ( $130$ xal): Əlavə məhdudiyyət yoxdur