304060: CF780A. Andryusha and Socks
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Andryusha and Socks
题意翻译
# 题目描述 $Andryusha$是一个有规划的男孩,他想把东西放在相应的地方。 今天,他面对着一个问题——把他的袜子~~(恶心)~~放进他的衣柜里。他有$n$双袜子,都在一个包里,并按$1$到$n$的顺序标了号,$Andryusha$想把它们找到它们的另外一半(两双本来是一起的袜子)并一起放进衣柜里。他先把袜子一个一个从他的包里拿出来,**与此同时**他寻找着桌上有没有一只袜子与另外一只袜子可以配对,如果可以,他就会把它们一起放进衣柜里。就这样,他把所有的袜子都整齐地放进了衣柜里。 $Andryusha$记得他放袜子的顺序。你能告诉他桌子上袜子最多的时候,袜子有几只? # 输入与输出 ## 输入 输入共两行,第一行代表着袜子的双数$n(1<=n<=10^5)$。 接下来一行,包含$2n$个整数:$x_1,x_2,x_3,…x_2n(1<=x_i<=n)$,表示了$Andryusha$放袜子的次序。 ## 输出 输出仅一行,代表桌子上袜子最多的时候袜子的只数。 ## 输入样例#1 1 1 1 ## 输出样例#1 1 ## 输入样例#2 3 2 1 1 3 2 3 ## 输出样例#2 2题目描述
Andryusha is an orderly boy and likes to keep things in their place. Today he faced a problem to put his socks in the wardrobe. He has $ n $ distinct pairs of socks which are initially in a bag. The pairs are numbered from $ 1 $ to $ n $ . Andryusha wants to put paired socks together and put them in the wardrobe. He takes the socks one by one from the bag, and for each sock he looks whether the pair of this sock has been already took out of the bag, or not. If not (that means the pair of this sock is still in the bag), he puts the current socks on the table in front of him. Otherwise, he puts both socks from the pair to the wardrobe. Andryusha remembers the order in which he took the socks from the bag. Can you tell him what is the maximum number of socks that were on the table at the same time?输入输出格式
输入格式
The first line contains the single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of sock pairs. The second line contains $ 2n $ integers $ x_{1},x_{2},...,x_{2n} $ ( $ 1<=x_{i}<=n $ ), which describe the order in which Andryusha took the socks from the bag. More precisely, $ x_{i} $ means that the $ i $ -th sock Andryusha took out was from pair $ x_{i} $ . It is guaranteed that Andryusha took exactly two socks of each pair.
输出格式
Print single integer — the maximum number of socks that were on the table at the same time.
输入输出样例
输入样例 #1
1
1 1
输出样例 #1
1
输入样例 #2
3
2 1 1 3 2 3
输出样例 #2
2