I. Preparing the Lunch
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Students participating in the ICPC are sitting evenly spaced around a round table for lunch. Each student has one catered lunch box. There are various types of lunch boxes, and not all students necessarily have the same type. The number of the students is even. Thus, for each student, there is exactly one student on the directly opposite seat of the table. The number of lunch boxes of each type is even.

As the lunch box on the seat directly opposite is easily visible, a student may feel envious if it is not of the same type as that student's own. Therefore, you want each pair of students sitting opposite each other to have the same type of lunch boxes. As the number of lunch boxes of each type is even, such an arrangement is always possible. To rearrange the lunch boxes, you repeat the following operation any number of times: select any pair of adjacent students and have them exchange their lunch boxes. Find the minimum number of such operations required to achieve the goal.

Input

The input consists of at most $$$5 \times 10^4$$$ test cases, each in the following format.

$$$n$$$
$$$a_{1}$$$ $$$\cdots$$$ $$$a_{2n}$$$

Each test case consists of two lines. The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2 \times 10^5),$$$ meaning that there are $$$2n$$$ students at the lunch table. The second line contains $$$2n$$$ integers $$$a_1, \ldots, a_{2n}.$$$ The $$$i$$$-th integer $$$a_i$$$ denotes the type of lunch box initially held by the $$$i$$$-th student $$$(i=1,\ldots, 2n),$$$ where the students are numbered clockwise around the table from a specific position. Each integer $$$a_i$$$ is between $$$1$$$ and $$$n,$$$ inclusive. For any integer $$$j,$$$ the number of indices $$$i$$$ such that $$$a_i=j$$$ is guaranteed to be even.

The end of the input is indicated by a line consisting only of a zero. The sum of $$$n$$$ over all the test cases does not exceed $$$2 \times 10^5.$$$

Output

For each test case, output in a line the minimum number of operations required to achieve the goal.

Example
Input
4
4 2 3 4 1 2 1 3
4
1 2 1 3 2 2 2 3
3
3 3 3 3 3 3
0
Output
2
3
0
Note

For the first test case, swapping the 1 at the seventh position with the 3 in the next position results in 4 2 3 4 1 2 3 1, and then swapping the 1 at the eighth position with the 4 at the first position results in 1 2 3 4 1 2 3 4. After these two swaps, all the pairs of lunch boxes at the direct opposite seats are of the same type. Since the goal cannot be achieved with a single swap, the answer is 2.