P5749 [IOI 2019] Arranging Shoes

Adnan owns the largest shoe store in Baku. A box containing $n$ pairs of shoes has just arrived at his store. Each pair of shoes consists of two shoes of the same size: one left shoe and one right shoe. Adnan lines up these $2n$ shoes in a row. This row has a total of $2n$ **positions**, numbered from $0$ to $2n-1$ from left to right. Adnan wants to rearrange these shoes into a **valid permutation**. A permutation is valid if and only if for all $i(0\leqslant i \leqslant n - 1)$, the following conditions all hold: - The shoes at positions $2i$ and $2i+1$ have the same size. - The shoe at position $2i$ is a left shoe. - The shoe at position $2i+1$ is a right shoe. To achieve this, Adnan can perform a sequence of swaps. In each swap, he chooses two currently **adjacent** shoes and swaps them (that is, he picks them up and puts each shoe back into the other shoe’s original position). Two shoes are adjacent if and only if the difference of their position indices is $1$. Find the minimum number of swaps Adnan needs to obtain a valid permutation.

The first line contains a positive integer $n$, meaning there are $n$ pairs of shoes. The second line contains $2n$ integers $S_i$. The $i$-th integer describes the shoe whose position index is $i-1$. Here $|S_u|\neq 0$, and it equals the size of the shoe initially at position $i$. Here $|x|$ denotes the absolute value of $x$: it equals $x$ when $x\geq 0$, and equals $-x$ when $x < 0$. If $S_i < 0$, then the shoe at position $i$ is a left shoe; otherwise, it is a right shoe.

Output one line with one integer, the minimum number of swaps.

**Explanation for Sample 1** Adnan can obtain a valid permutation with $4$ swaps. For example, he can first swap $1$ and $-1$, then swap $1$ and $-2$, then swap $-1$ and $-2$. Finally, swap $-2$ and $2$. After that, he can get a valid permutation. It is impossible to obtain a valid permutation with fewer than $4$ swaps, so the output is $4$.  **Explanation for Sample 2** Adnan can swap the shoes at positions $2$ and $3$ to obtain the valid permutation $[-2,2,-2,2,-2,2]$, so the output should be $1$. **Constraints** For all testdata: - $1\leqslant n\leqslant10^5$. - For all $i(0\leqslant i\leqslant 2n-1)$, $1\leqslant \left|S_{i+1}\right|\leqslant n$. - A valid permutation can always be obtained through a sequence of swaps. The detailed extra constraints and scores for subtasks are shown in the table below: | Subtask ID | Additional Constraints | Score | |:---:|:---:|:---:| | $1$ | $n=1$ | $10$| |$2$|$n\leqslant8$|$20$| |$3$| All shoes have the same size. | $20$| |$4$| All shoes at positions $0,\dots,n-1$ are left shoes, and all shoes at positions $n,\dots,2n-1$ are right shoes. Also, for all $i(0\leqslant i\leqslant n-1)$, the shoes at positions $i$ and $i+n$ have the same size. | $15$| |$5$|$n\leqslant10^3$|$20$| |$6$| No additional constraints. | $15$| Translated by ChatGPT 5