A survey rover moves along a straight corridor and logs the ID of every beacon it detects, in the exact order of detection. Over the course of its run, some beacon IDs are picked up far more often than others.

Define the corridor's dominance count as the largest number of times any single beacon ID appears anywhere in the full log. Your task is to find the length of the shortest contiguous block of the log (a run of consecutive detections) whose own most-repeated beacon ID appears exactly that many times — a block that reproduces the corridor's dominance count using as few consecutive detections as possible.

Input format

• Line 1: a single integer n, the number of detections.
• Line 2: n space-separated integers id_1 id_2 ... id_n, the beacon ID logged at each step, in order.

Output format

A single integer: the length of the shortest contiguous block whose maximum internal repeat count equals the corridor's overall dominance count.

Constraints

• 1 <= n <= 50000
• 0 <= id_i <= 49999

5
1 2 2 3 1

2

7
1 2 2 3 1 4 2

6