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)在桌子上。安德留莎从第三双中拿出一只袜子,把这双放进衣柜里。