Duplicate Number :
Difficulty Level : Easy
Submissions : 499
Asked In :
Marks :10
: 3 | : 0
Given an array of integers $$$nums$$$ containing $$$n$$$ + $$$1$$$ integers where each integer is in the range $$$[1, n]$$$ inclusive.
There is only one repeated number that occurs twice in $$$nums$$$, return this repeated number.
Try to solve the problem without modifying the array $$$nums$$$ and using only constant extra space.
Input
The first line contains an integer $$$n$$$. The second line contains $$$n$$$ + $$$1$$$ integers where each integer is in range $$$1$$$ to $$$n$$$.$$$(1 \le n \le 10^5).$$$
Output
Output a single integer that is repeated.
Examples
Input
3 1 2 3 3
Output
3
Input
4 1 2 1 4 3
Output
1
Input
7 1 2 3 4 5 6 7 4
Output
4
