Tightest rescan: hints, no solution

At the dock gate, scans are numbered by position in the day's log, starting at position 0. The same pallet id can be scanned more than twice, for instance when a pallet loops between two conveyors.

Find the smallest distance between the log positions of two scans that carry the same pallet id, where the distance between positions i and j is j minus i. Only scans of the same id may be paired, and any two of an id's scans count, not just the first two. If no id occurs twice, return -1.

Examples

Input

scans = [5, 1, 5, 2, 1, 5]

Output

2

Note

Id 5 sits at positions 0, 2 and 5, so its closest pair is 0 and 2, distance 2.

Input

scans = [3, 4, 5]

Output

-1

Note

No id occurs twice.

Input

scans = [8, 8]

Output

1

Note

Two neighbouring scans give distance 1.

Constraints

• 0 <= scans.length <= 140000
• 1 <= scans[i] <= 1000000
• Positions are zero-based; return -1 if no repeat

Hint 1: a nudge

For one scan, which earlier scans are worth comparing it with, and which are wasted effort?

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