Wookje's Dinner Wheel

Time limit2sMemory limit256 MB

Summary

Given a sequence where each menu number appears exactly twice, find the maximum number of values seen once but not yet seen twice at any point.

Level: Medium4 of 10
Topics: Array, Hash map, Simulation, Greedy
Solved: No attempts yet

Problem

Wookje spends time every evening deciding what to eat. He is tired of repeating the same decision, so he settles the dinner menu for $N$ days at once.

Wookje prepares $N$ distinct menus and one large wheel. He splits the wheel into $N$ cells of equal size and writes one menu on each cell. A cell holds exactly one menu, and a menu is written on exactly one cell.

Wookje spins the wheel by these rules.

Spin the wheel and check the cell it stops on.
If that cell has no sticker, put one sticker on it.
If that cell already has a sticker, write the menu of that cell on the meal plan, peel the sticker off, and remove the cell. Wookje's wheel is special, so it never stops on a removed cell again.
Repeat steps 1 to 3 until every cell is removed.

Under these rules, $2N$ spins settle all $N$ days of menus. The result of every spin is given in order. Find the largest number of stickers that were on the wheel at the same time.

Input

The first line contains the number of menus $N$ ( $1 \le N \le 10^5$ ).

The second line contains $2N$ menu numbers separated by spaces, the numbers written on the cells the wheel stopped on, in spin order. Each menu number is an integer between $1$ and $N$ , and each number appears exactly twice.

Output

Print the largest number of stickers that were on the wheel at the same time.

Examples2

Example 1
Input
```
3
1 3 3 2 1 2
```
Expected output
```
2
```
Example 2
Input
```
5
1 1 2 2 3 3 4 4 5 5
```
Expected output
```
1
```