English · Original
Chinese · Translation
Formal · Original
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?
## Input
The first line contains the single integer _n_ (1 ≤ _n_ ≤ 105) — the number of sock pairs.
The second line contains 2_n_ integers _x_1, _x_2, ..., _x_2_n_ (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.
## Output
Print single integer — the maximum number of socks that were on the table at the same time.
[samples]
## Note
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.
Andryusha 是一个有条理的男孩，喜欢把东西放回原位。
今天他面临一个难题：把袜子放进衣柜。他有 #cf_span[n] 双不同的袜子，最初都放在一个袋子里。这些袜子对编号从 #cf_span[1] 到 #cf_span[n]。Andryusha 希望将成对的袜子放在一起并放入衣柜。他一个接一个地从袋子里取出袜子，对于每只袜子，他会查看这只袜子的配对是否已经被取出。如果没有（意味着它的配对仍在袋子里），他就把当前这只袜子放在面前的桌子上。否则，他就把这对袜子一起放进衣柜。
Andryusha 记住了他从袋子里取袜子的顺序。你能告诉他，同时出现在桌子上的袜子的最大数量是多少吗？
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——袜子对的数量。
第二行包含 #cf_span[2n] 个整数 #cf_span[x1, x2, ..., x2n]（#cf_span[1 ≤ xi ≤ n]），描述 Andryusha 从袋中取袜子的顺序。更准确地说，#cf_span[xi] 表示第 #cf_span[i] 只被取出的袜子属于第 #cf_span[xi] 对。
保证 Andryusha 每对袜子恰好取了两只。
请输出一个整数——同时出现在桌子上的袜子的最大数量。
在第一个例子中，Andryusha 取出第一对中的一只袜子并放在桌子上。然后他取出下一只袜子，它也属于第一对，于是他立即将这对袜子放进衣柜。因此，同时在桌子上的袜子最多为一只。
在第二个例子中，Andryusha 的行为如下：
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——袜子对的数量。
第二行包含 #cf_span[2n] 个整数 #cf_span[x1, x2, ..., x2n]（#cf_span[1 ≤ xi ≤ n]），描述 Andryusha 从袋中取袜子的顺序。更准确地说，#cf_span[xi] 表示第 #cf_span[i] 只被取出的袜子属于第 #cf_span[xi] 对。
保证 Andryusha 每对袜子恰好取了两只。
## Output
请输出一个整数——同时出现在桌子上的袜子的最大数量。
[samples]
## Note
在第一个例子中，Andryusha 取出第一对中的一只袜子并放在桌子上。然后他取出下一只袜子，它也属于第一对，于是他立即将这对袜子放进衣柜。因此，同时在桌子上的袜子最多为一只。
在第二个例子中，Andryusha 的行为如下：
最初桌子是空的，他取出一双编号为 #cf_span[2] 的袜子并放在桌子上。
桌子上有袜子 #cf_span[(2)]。Andryusha 取出一双编号为 #cf_span[1] 的袜子并放在桌子上。
桌子上有袜子 #cf_span[(1, 2)]。Andryusha 取出另一只编号为 #cf_span[1] 的袜子，并将这对袜子放进衣柜。
桌子上有袜子 #cf_span[(2)]。Andryusha 取出一双编号为 #cf_span[3] 的袜子并放在桌子上。
桌子上有袜子 #cf_span[(2, 3)]。Andryusha 取出另一只编号为 #cf_span[2] 的袜子，并将这对袜子放进衣柜。
桌子上有袜子 #cf_span[(3)]。Andryusha 取出另一只编号为 #cf_span[3] 的袜子，并将这对袜子放进衣柜。
因此，同时在桌子上的袜子最多为两只。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of sock pairs.
Let $ X = (x_1, x_2, \dots, x_{2n}) $ be a sequence of integers where $ x_i \in \{1, 2, \dots, n\} $, representing the pair number of the $ i $-th sock taken from the bag.
Each pair $ j \in \{1, \dots, n\} $ appears exactly twice in $ X $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq x_i \leq n $ for all $ i \in \{1, \dots, 2n\} $
3. For each $ j \in \{1, \dots, n\} $, $ |\{i \mid x_i = j\}| = 2 $
**Objective**
Simulate the process:
- Maintain a set $ T \subseteq \{1, \dots, n\} $ of pair numbers currently on the table.
- For each $ i = 1 $ to $ 2n $:
- If $ x_i \notin T $, add $ x_i $ to $ T $.
- Else, remove $ x_i $ from $ T $.
Compute $ \max_{i \in \{1, \dots, 2n\}} |T| $ after processing each sock.
Output: $ \max_{i} |T_i| $, where $ T_i $ is the state of $ T $ after processing the $ i $-th sock.
API Response (JSON)
{
"problem": {
"name": "A. Andryusha and Socks",
"description": {
"content": "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 pa",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF780A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Andryusha is an orderly boy and likes to keep things in their place.\n\nToday 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 pa...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Andryusha 是一个有条理的男孩，喜欢把东西放回原位。\n\n今天他面临一个难题：把袜子放进衣柜。他有 #cf_span[n] 双不同的袜子，最初都放在一个袋子里。这些袜子对编号从 #cf_span[1] 到 #cf_span[n]。Andryusha 希望将成对的袜子放在一起并放入衣柜。他一个接一个地从袋子里取出袜子，对于每只袜子，他会查看这只袜子的配对是否已经被取出。如果没有（意味着它的配对...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of sock pairs. \nLet $ X = (x_1, x_2, \\dots, x_{2n}) $ be a sequence of integers where $ x_i \\in \\{1, 2, \\dots, n\\} $, representing the pair ...",
"is_translate": false,
"language": "Formal"
}
]
}