Fişierul intrare/ieşire:	twinperms.in, twinperms.out	Sursă	Algoritmiada 2022, Runda 1
Autor	Tinca Matei	Adăugată de	Tinca Matei •TincaMatei
Timp execuţie pe test	0.125 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Twinperms

Zi-mi ce alegi: ori ne-apărăm spatele, ori ni-l înjunghiem

Georgian şi Ştefan, căutând în 3 camere din casă, au găsit două permutări gemene, p şi q, de mărime N. Atunci când cineva interschimba elementele de pe poziţiile i şi j dintr-o permutare, în paralel se interschimbau şi elementele de pe aceleaşi poziţii în cealaltă permutare. De exemplu, dacă cele două permutări sunt: p = [2, 1, 3] şi q = [3, 2, 1], atunci prin interschimbarea elementelor de pe poziţiile 1 şi 3, atunci permutările devin p = [3, 1, 2] şi q = [1, 2, 3]. Ei pot aplica oricâte interschimbări de acest fel.

Şi Georgian şi Ştefan vor să îşi minimizeze numărul de inversiuni al permutărilor fiecăruia, dar pentru că de fiecare dată când cineva schimbă ceva la o permutare, se schimbă şi în cealaltă, atunci ei s-au decis să facă astfel încât numărul de inversiuni în total din ambele permutări să fie cât mai mic.

Cerinţă

Dându-se două permutări de mărime N, calculaţi suma minimă a numărului de inversiuni din cele două permutări după ce se aplică operaţia de interschimbare descrisa mai sus de oricâte ori.

Date de intrare

Fişierul de intrare twinperms.in, pe prima linie se găseşte numărul N, ce reprezintă mărimile celor două permutări.
Pe următoarele două linii se află câte N elemente, reprezentând cele două permutări p şi q.

Date de ieşire

În fişierul de ieşire twinperms.out se va afişa un singur număr ce reprezintă suma minimă a numărului de inversiuni din cele două permutări.

Restricţii

• Permutările sunt indexate de la 1 până la N.
• 1 ≤ N ≤ 100.000.
• Pentru 10 puncte, avem p_i = q_i pentru toate i, unde 1 ≤ i ≤ N.
• Pentru alte 10 puncte, avem p_i + q_i = N + 1 pentru toate i, unde 1 ≤ i ≤ N.
• Pentru alte 10 puncte, avem 1 ≤ N ≤ 9.
• Pentru alte 15 puncte, avem 1 ≤ N ≤ 16.
• Pentru alte 35 de puncte, avem 1 ≤ N ≤ 3.000.
• O permutare de mărime N este un şir de N elemente unde fiecare număr de la 1 până la N apare exact o dată.
• Numărul de inversiuni dintr-o permutare p este numărul de perechi i, j, unde 1 ≤ i < j ≤ N, cu proprietatea că p_i > p_j.

Exemplu

Explicaţie

Putem să interschimbăm elementele de pe poziţiile 1 şi 3, astfel permutările devin: p = [1, 4, 3, 2] şi q = [2, 4, 1, 3]. După asta, putem interschimba elementele de pe poziţiile 2 şi 3, astfel permutările devin: p = [1, 3, 4, 2] şi q = [2, 1, 4, 3]. La sfârşit, putem interschimba elementele de pe poziţiie 3 şi 4. Permutările vor ajunge în final: p = [1, 3, 2, 4] şi q = [2, 1, 3, 4]. Cum prima permutare are o inversiune, şi anume cea de pe poziţiile 2 şi 3, iar a doua permutare are tot o singură inversiune, şi anume cea de pe poziţiile 1 şi 2, numărul total de inversiuni va fi 2. Această sumă este minimă.

Cum se trimit solutii?