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

说明

In the first example Andryusha took a sock from the first pair and put it on the table. Then he took the next sock which is from the first pair as well, so he immediately puts both socks to the wardrobe. Thus, at most one sock was on the table at the same time. In the second example Andryusha behaved as follows: - Initially the table was empty, he took out a sock from pair $ 2 $ and put it on the table. - Sock $ (2) $ was on the table. Andryusha took out a sock from pair $ 1 $ and put it on the table. - Socks $ (1,2) $ were on the table. Andryusha took out a sock from pair $ 1 $ , and put this pair into the wardrobe. - Sock $ (2) $ was on the table. Andryusha took out a sock from pair $ 3 $ and put it on the table. - Socks $ (2,3) $ were on the table. Andryusha took out a sock from pair $ 2 $ , and put this pair into the wardrobe. - Sock $ (3) $ was on the table. Andryusha took out a sock from pair $ 3 $ and put this pair into the wardrobe. Thus, at most two socks were on the table at the same time.

Input

题意翻译

# 题目描述 $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

加入题单

上一题 下一题 算法标签: