[R77C]文件 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有一个文件堆和 $n$ 份文件，文件依次编号为 $1,2,\ldots,n$。初始时，文件堆为空。

给定一个长度为 $2n$ 的序列 $a$，每个编号 $1,2,\ldots,n$ 都在序列中恰好出现两次。你需要从左到右依次处理序列中的每个元素：

• 当编号 $x$ 第一次出现时，将编号为 $x$ 的文件放到文件堆的顶部；
• 当编号 $x$ 第二次出现时，从文件堆中取出编号为 $x$ 的文件。文件可以从文件堆中的任意位置直接取出，取出后，其余文件之间的相对顺序保持不变。

若取出某份文件前，该文件恰好位于文件堆的顶部，则称这次取件为一次无遮挡取件。

请计算处理完整个序列后，无遮挡取件的总次数。

格式

输入格式

第一行包含一个整数 $n$，表示文件的数量。

第二行包含 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$，表示需要依次处理的编号序列。

输出格式

输出一行一个整数，表示无遮挡取件的总次数。

样例

样例输入 #1

3
1 2 2 3 3 1

样例输出 #1

3

样例解释 #1

编号 $2$、$3$ 和 $1$ 的文件被取出前均位于文件堆顶部，因此共有 $3$ 次无遮挡取件。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$50$	$5000$
$2$	$50$	$2\times 10^5$

对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le a_i\le n$，且每个整数 $1,2,\ldots,n$ 在序列 $a$ 中恰好出现两次。