← 返回题目列表

Codeforces · 780/A

A. Andryusha 和袜子

中文机器翻译题面 查看原题

Andryusha 是一个遵守秩序的男孩,喜欢把东西放在原处。

今天他遇到了将袜子放入衣柜的问题。他有 n 双不同的袜子,最初放在一个袋子里。这些对从 1 到 n 编号。 Andryusha 想要将配对的袜子放在一起并放入衣柜中。他把袜子一只一只地从袋子里取出来,对于每只袜子,他都会检查这双袜子是否已经从袋子里取出来。如果没有(这意味着这双袜子仍在袋子里),他将当前的袜子放在他面前的桌子上。否则,他会把这双袜子中的两只袜子都放到衣柜里。

Andryusha 记得他从包里取出袜子的顺序。你能告诉他桌子上同时最多有多少只袜子吗?

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — 袜子对的数量。

第二行包含 2n 个整数 x1, x2, ..., x2n (1 ≤ xi ≤ n),描述了 Andryusha 从包里取出袜子的顺序。更准确地说,xi 表示 Andryusha 取出的第 i 只袜子来自第 xi 对。

保证 Andryusha 拿走了每双中的两只袜子。

输出

打印单个整数 — 桌子上同时出现的袜子的最大数量。

示例

输入 #1

1
1 1

输出 #1

1

输入 #2

3
2 1 1 3 2 3

输出 #2

2

注意

在第一个示例中,Andryusha 从第一双中取出一只袜子并将其放在桌子上。然后他又拿了第一双的第二只袜子,所以他立即把两只袜子都放进了衣柜。因此,同一时间桌上最多只有一只袜子。

在第二个示例中,Andryusha 的行为如下:

- 最初桌子是空的,他从第二双中拿出一只袜子放在桌子上。
- 袜子(2)在桌子上。安德留莎从第一双中拿出一只袜子,放在桌子上。
- 袜子(1, 2)在桌子上。安德留莎从第一双中拿出一只袜子,把这双放进衣柜里。
- 袜子(2)在桌子上。安德留莎从第三对中拿出一只袜子,放在桌子上。
- 袜子(2, 3)在桌子上。安德留莎从第二双中拿出一只袜子,把这双放进衣柜里。
- 袜子(3)在桌子上。安德留莎从第三双中拿出一只袜子,把这双放进衣柜里。