You are given an array of integers nums containing n + 1 integers. Each integer in nums is in the range [1, n] inclusive.

Every integer appears exactly once, except for one integer which appears two or more times. Return the integer that appears more than once.

Examples

Example 1

Input:  nums = [1,2,3,2,2]
Output: 2

Example 2

Input:  nums = [1,2,3,4,4]
Output: 4

Constraints

• 1 <= n <= 10000
• nums.length == n + 1
• 1 <= nums[i] <= n