Description

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.

Input Format

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 Format

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

2
2 1 -1 -2

4

3
-2 2 2 -2 -2 2

1

Hint

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:

Translated by ChatGPT 5