#QY0055. 袜子收纳

袜子收纳

小核桃是一个有强迫症的机器人,喜欢将事物都保持规律,但是他在将袜子放到衣柜里时遇到了问题。

他有 nn 双不同的袜子,最初是放在袋子里的,这些袜子成对从 11nn 编号。小核桃希望将成对的袜子放在一起,然后放到衣柜里。他从袋子里一只只地拿出袜子,然后为每只袜子看这双袜子是否都已经从袋子里拿出来了。如果不是(这意味着这双袜子的另一只仍在袋子里),他会将当前的袜子放在他面前的桌子上。否则,他会将这双袜子都放到衣柜里。

小核桃记得他从袋子​​里取出袜子的顺序。您能告诉他在桌子上最多同时放了多少只袜子吗?

输入

第一行包含单个整数 nn(1n2e4) (1 \le n \le 2e4) 即袜子对的数量。

第二行包含 2n 2 \cdot n 个整数 x1,x2,...,x2n (1xin) x_1 , x_2 , ... , x_{2 \cdot n}\ (1 \le x_i \le n),它们描述了从袋子中取出袜子的顺序。更准确地说, xix_i 表示取出的第 ii 只袜子来自 xix_i 对。

可以肯定的是,小核桃的每双袜子正好有两只。

输出

打印单个整数,即桌子上同时存在的最大袜子数。

样例

1
1 1
1
3
2 1 1 3 2 3
2

提示

对于 100%100\% 的数据,1n2e41 \le n \le 2e4

在第一个示例中,小核桃从第一对袜子中取出一只袜子放在桌子上。 然后,他拿起了第一双袜子中的第二只袜子,此时他将两只袜子放到衣柜里。 因此,同一时间最多只有一张袜子在桌子上。

在第二个示例中,小海狸的行为如下:

最初桌子是空的,他取出一只袜子2放在桌子上。

袜子 22 在桌子上。 从第一双中取出一只袜子,放在桌子上。

桌上放着袜子 1,21, 2 。 从第 22 对中取出袜子,然后将这对放入衣柜。

袜子 22 在桌子上。 从第 33 对袜子中取出一只袜子,放在桌上。

桌上放着袜子 2,32, 3 。 从第 22 对袜子中取出一只袜子,然后将其放入衣柜。

袜子 33 在桌子上。 从第 33 对中取出一只袜子,将这对放入衣柜。

因此,最多只能同时将两只袜子放在桌子上。

建议时间复杂度

建议算法时间复杂度:O(2n)O(2 \cdot n)