Fermat's Fakini

Interview

Time limit1sMemory limit2048 MB

Summary

Given N nicknames split into even and odd gangs, Mirko joins the larger gang and picks the smallest unused natural number with that parity.

Level: Easy2 of 10
Topics: Implementation, Hash map
Solved: No attempts yet

Problem

For centuries, ~~Pavlov~~Fermat Street has been ruled by two gangs, even-shirts and odd-shirts1. The names are no accident. Every boy in the even-shirts has a nickname that is an even natural number, and every boy in the odd-shirts has a nickname that is an odd natural number. Every boy who lives on Fermat Street belongs to one of the two gangs.

Mirko moved to Fermat Street today and must choose a gang to join. He decided it is better to join the bigger gang. For his nickname, he will pick the smallest natural number that is not yet taken, that is, the smallest natural number such that no boy in the gang he joins has that nickname. Print the nickname Mirko picks.

1 After the contest, be sure to read the novel Junaci Pavlove ulice by Ferenc Molnar.

Input

The first line contains a natural number $N$ ( $1 \le N \le 100$ ), the number of boys (not counting Mirko) who live on Fermat Street. You may assume the two gangs do not have the same number of members.

The second line contains $N$ natural numbers less than $1\,000\,000$ , where the $i$ -th number is the nickname of the $i$ -th boy.

Output

Print Mirko's nickname on a single line.

Hint

Explanation of the third sample: there are two even-shirts and three odd-shirts, so Mirko becomes an odd-shirt. His nickname is $1$ , the smallest odd natural number, and nobody has that nickname.

Examples3

Example 1
Input
```
3
10 12 4
```
Expected output
```
2
```
Example 2
Input
```
5
20 2 22 2020 2002
```
Expected output
```
4
```
Example 3
Input
```
5
9 2 7 4 11
```
Expected output
```
1
```