#QY0055. 袜子收纳
袜子收纳
小核桃是一个有强迫症的机器人,喜欢将事物都保持规律,但是他在将袜子放到衣柜里时遇到了问题。
他有 双不同的袜子,最初是放在袋子里的,这些袜子成对从 到 编号。小核桃希望将成对的袜子放在一起,然后放到衣柜里。他从袋子里一只只地拿出袜子,然后为每只袜子看这双袜子是否都已经从袋子里拿出来了。如果不是(这意味着这双袜子的另一只仍在袋子里),他会将当前的袜子放在他面前的桌子上。否则,他会将这双袜子都放到衣柜里。
小核桃记得他从袋子里取出袜子的顺序。您能告诉他在桌子上最多同时放了多少只袜子吗?
输入
第一行包含单个整数 即袜子对的数量。
第二行包含 个整数 ,它们描述了从袋子中取出袜子的顺序。更准确地说, 表示取出的第 只袜子来自 对。
可以肯定的是,小核桃的每双袜子正好有两只。
输出
打印单个整数,即桌子上同时存在的最大袜子数。
样例
1
1 1
1
3
2 1 1 3 2 3
2
提示
对于 的数据, 。
在第一个示例中,小核桃从第一对袜子中取出一只袜子放在桌子上。 然后,他拿起了第一双袜子中的第二只袜子,此时他将两只袜子放到衣柜里。 因此,同一时间最多只有一张袜子在桌子上。
在第二个示例中,小海狸的行为如下:
最初桌子是空的,他取出一只袜子2放在桌子上。
袜子 在桌子上。 从第一双中取出一只袜子,放在桌子上。
桌上放着袜子 。 从第 对中取出袜子,然后将这对放入衣柜。
袜子 在桌子上。 从第 对袜子中取出一只袜子,放在桌上。
桌上放着袜子 。 从第 对袜子中取出一只袜子,然后将其放入衣柜。
袜子 在桌子上。 从第 对中取出一只袜子,将这对放入衣柜。
因此,最多只能同时将两只袜子放在桌子上。
建议时间复杂度
建议算法时间复杂度: 。