Longest run of consecutive numbers

Problem

A ticket collector has a pile of ticket numbers in no order, with some repeats. Find the length of the longest group of numbers that are consecutive, like 4 5 6 7, using each ticket number once. The tickets in the group do not need to be next to each other in the pile.

Input, output and limits

Input: The first line has n. The second line has n integers: the ticket numbers.
Output: The length of the longest run of consecutive numbers.
Constraints: 1 ≤ n ≤ 10^5
-10^9 ≤ ticket ≤ 10^9

Examples

Example 1

Input

6
100 4 200 1 3 2

Output

1 2 3 4 is the longest run.

Example 2

Input

7
5 6 6 7 2 5 8

Output

Repeats do not break or extend a run: 5 6 7 8.

Hints

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

Hint 1

Sort the numbers first: a run then sits side by side.

Hint 2

Walk the sorted array. If a number equals the one before, skip it. If it is one more, the run grows. Otherwise a new run starts at length 1.

Hint 3

Remember the best run length seen so far.

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

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems