样例下载

题目描述

$n$ 对括号被打乱了顺序，排成一个字符串。

每对括号有一种类型，比如一对圆括号，一对方括号，一对花括号，等等。我们用 $1$ ~ $n$ 之间的一个整数表示一种类型，比如 1 代表圆括号，2 代表方括号，……。

现在想要重排这些括号，从而得到一个合法的括号序列。

所谓合法的括号序列，是指从左到右每两个括号为一组均可以形成合法的括号对。所谓合法的括号对，是指两个括号的类型相同，且左括号在左，右括号在右。

你可以进行以下操作：

每次操作，你可以选择任意两个相邻的括号，交换它们的位置。

你可以操作任意次。

问：你至少操作多少次，可以使得括号序列合法。

输入格式

第一行：一个整数 $n$。

第二行：包含 $2n$ 个整数 $A_i$ 用来描述括号序列。$|A_i|$ 表示括号的类型。$A_i < 0$ 表示左数第 $i$ 个括号是类型为 $|A_i|$ 的左括号，否则是类型为 $|A_i|$ 的右括号。

输出格式

一个整数，表示答案。

样例1输入

3
3 -1 1 -3 -6 6

样例1输出

3

样例1解释

3 -1 1 -3 -6 6

第 1 次操作：3 -1 1 -3 -6 6 ===> -1 3 1 -3 -6 6

第 2 次操作：-1 3 1 -3 -6 6 ===> -1 1 3 -3 -6 6

第 3 次操作：-1 1 3 -3 -6 6 ===> -1 1 -3 3 -6 6

样例2输入

3
-1 1 1 -1 -1 1

样例2输出

1

数据范围

100% 的数据：$1 ≤ n ≤ 10^5$, $1 ≤ |A_{i}| ≤ n$, 数据保证有解。

子任务编号	附加限制	分值
$1$	$n=1$	$10$
$2$	$1 ≤ n ≤ 8$	$20$
$3$	所有括号类型都是相同的	$20$
$4$	前 $n$ 个括号全部是左括号，后 $n$ 个括号全部是右括号。而且对于所有 $i(1 ≤ i ≤ n)$，在位置 $i$ 和 $i+n$ 的括号类型相同	$15$
$5$	$1 ≤ n ≤ 10^3$	$20$
$6$	$1 ≤ n ≤ 10^5$, $1 ≤ |A_{i}| ≤ n$	$15$