Duplicated number

Time limit2sMemory limit256 MB

Summary

A size-N array contains 1..N-1 with one value M repeated; find M.

Level: Easy3 of 10
Topics: Math
Solved: No attempts yet

Problem

A sequence holds every integer from $1$ to $N-1$ exactly once, in no particular order. One more integer $M$ with $1 \le M \le N-1$ is put into it, which makes a sequence $A$ of size $N$ . Given $A$ , write a program that finds $M$ .

Input

The first line contains the size $N$ of the sequence $A$ ( $2 \le N \le 10\,000\,000$ ).

The second line contains the $N$ elements of $A$ , separated by spaces. Every element is an integer between $1$ and $N-1$ , and all of them are distinct except the answer $M$ .

Output

Print $M$ on the first line.

Examples5

Example 1
Input
```
10
1 2 2 5 6 4 3 7 8 9
```
Expected output
```
2
```
Example 2
Input
```
2
1 1
```
Expected output
```
1
```
Example 3
Input
```
3
1 1 2
```
Expected output
```
1
```
Example 4
Input
```
5
4 1 3 2 4
```
Expected output
```
4
```
Example 5
Input
```
7
3 6 1 5 3 2 4
```
Expected output
```
3
```