Dispatch run with one holiday: hints, no solution

A depot keeps the day numbers on which it dispatched at least one truck. The list is in no particular order and a day can be listed twice.

A dispatch run is a stretch of consecutive day numbers in which every day has a dispatch, except that the depot may skip exactly one day inside the stretch, a holiday, provided the days on both sides of the hole are present. A run may also use no holiday at all. Return the most dispatch days that a single run can contain. The holiday itself is not counted and each day counts once. Return 0 for an empty list.

Examples

Input

days = [8, 3, 5, 4, 7, 9, 20]

Output

6

Note

Days 3 to 5 and 7 to 9 are joined by holiday day 6, giving 6 dispatch days.

Input

days = [10, 4, 5, 12, 11, 7, 6]

Output

4

Note

Days 8 and 9 are missing, which is two holidays, so the runs stay separate and the longer has 4 days.

Input

days = [5, 5, 5]

Output

1

Note

Duplicates count once.

Constraints

• 0 <= days.length <= 250100
• 1 <= days[i] <= 1000000
• Only one missing day may be bridged in a run

Hint 1: a nudge

If you knew for one day whether the day before it is present, what would that tell you about where a run begins?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing