Longest Consecutive Run

HardArrayHashingUnion-Find5 hidden tests

Given an unsorted array of integers, find the length of the longest run of consecutive integers that all appear in the array (order and duplicates in the array do not matter).

Input format

Line 1: an integer n. Line 2: n space-separated integers (present whenever n >= 1).

Output format

One line: the length of the longest consecutive integer run.

Constraints

1 <= n <= 100000
-1000000000 <= each value <= 1000000000

Examples

Example 1

Input

6
100 4 200 1 3 2

Expected

Explanation

The run 1,2,3,4 is present, giving length 4; 100 and 200 are isolated.

Example 2

Input

3
5 5 5

Expected

Explanation

Only the value 5 is present, so the longest consecutive run has length 1.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →