Lollipop

Interview

Time limit4sMemory limit1024 MB

Summary

Find the shortest contiguous piece in which some flavor appears at least three times, or report NIE if no such piece exists.

Level: Medium5 of 10
Topics: Sliding window, Hash map
Solved: No attempts yet

Problem

Bajtek walked into a candy shop. A long lollipop made of $N$ parts of equal length caught his eye. Each part has a certain flavor.

Bajtek wants to pick a contiguous piece of this lollipop. To do so, he may break off some number of parts (possibly zero) from the left end and from the right end. The figure below shows several ways to pick pieces from the lollipop above. The pieces in the figure are marked with black frames.

Bajtek considers a piece tasty if it contains at least three parts with the same flavor. He does not care which flavor appears three times, or how many different flavors the piece has. All pieces in the figure above are tasty.

Bajtek does not want to overeat, so he wants the shortest tasty piece, meaning the piece made of the fewest parts. Write a program that finds the length of the shortest tasty piece of the lollipop described in the input, or reports that no tasty piece can be picked.

Input

The first line contains a natural number $N$ ( $1 \le N \le 500\,000$ ), the number of parts of the lollipop. The second line, which is also the last line, describes the lollipop with $N$ natural numbers $A_i$ ( $1 \le A_i \le 10^9$ ), the flavors of the parts from left to right. Different flavors are written as different numbers.

Output

Print one integer, the minimum number of parts in a tasty piece. If no tasty piece can be picked, print only the word NIE.

Examples4

Example 1
Input
```
10
6 8 4 8 6 8 8 2 6 6
```
Expected output
```
4
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
NIE
```
Example 3
Input
```
5
1 1 1 1 1
```
Expected output
```
3
```
Example 4
Input
```
7
9 99 999 9 999 99 9
```
Expected output
```
7
```