Find the missing roll number

Problem

A class has roll numbers 1 to n. The attendance sheet has n - 1 different roll numbers, in any order: exactly one student is absent. Find the missing roll number.

Input, output and limits

Input: The first line has n. The second line has n - 1 integers: the roll numbers present.
Output: The missing roll number.
Constraints: 1 ≤ n ≤ 10^5
The n - 1 numbers are different and each is from 1 to n.

Examples

Example

Input

6
3 1 6 2 5

Output

1 + 2 + … + 6 = 21, and the present numbers add up to 17.

Hints

Try the problem first. Open one hint at a time.

Hint 1

The sum 1 + 2 + … + n is n × (n + 1) / 2.

Hint 2

Subtract the sum of the numbers present. Use long, because n × (n + 1) can pass the int limit.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

Even numbers first, each part sortedmedium
Rotate a queue right by kmedium
Insertion sort, step by stepmedium
Remove repeats, keep first ordermedium
Selection sort, pass by passmedium

All Java problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems