막대 사탕

면접 대비

시간 제한4초메모리 제한1024 MB

요약

같은 맛이 세 번 이상 나오는 가장 짧은 연속 구간의 길이를 구합니다. 그런 구간이 없으면 NIE를 출력합니다.

난이도: 보통10점 중 5점
유형: 슬라이딩 윈도우, 해시맵
정답자: 아직 제출이 없습니다

문제

바이텍은 과자점에 갔다. 그의 눈길을 끈 것은 길이가 같은 $N$ 개의 부분으로 이루어진 긴 막대 사탕이었다. 각 부분에는 정해진 맛이 하나씩 있다.

바이텍은 막대 사탕에서 연속된 조각 하나를 고르고 싶어 한다. 이를 위해 왼쪽 끝과 오른쪽 끝에서 원하는 만큼 부분을 떼어 낼 수 있다(0개일 수도 있다). 아래 그림은 위 막대 사탕에서 조각을 고르는 여러 방법을 보여 준다. 그림의 조각은 검은 테두리로 표시되어 있다.

바이텍은 조각 안에 같은 맛인 부분이 세 개 이상 있으면 맛있다고 본다. 세 번 나오는 맛이 무엇인지, 조각에 맛이 몇 종류 있는지는 상관없다. 위 그림의 조각은 모두 맛있다.

바이텍은 과식하고 싶지 않아서 맛있는 조각 중 부분 개수가 가장 적은 것을 고르려 한다. 입력으로 주어진 막대 사탕에서 가장 짧은 맛있는 조각의 길이를 구하거나, 맛있는 조각을 고를 수 없다는 사실을 알려주는 프로그램을 작성하라.

입력

첫째 줄에 자연수 $N$ ( $1 \le N \le 500\,000$ )이 주어진다. $N$ 은 막대 사탕의 부분 개수이다. 둘째(마지막) 줄에는 막대 사탕의 설명이 주어진다. 왼쪽에서 오른쪽 순서대로 각 부분의 맛을 나타내는 자연수 $N$ 개 $A_i$ ( $1 \le A_i \le 10^9$ )가 주어진다. 서로 다른 맛은 서로 다른 수로 나타낸다.

출력

첫째 줄에 맛있는 조각 중 부분 개수가 가장 적은 조각의 부분 개수를 정수로 출력한다. 맛있는 조각을 고를 수 없으면 NIE만 출력한다.

예제4

예제 1
입력
```
10
6 8 4 8 6 8 8 2 6 6
```
예상 출력
```
4
```
예제 2
입력
```
5
1 2 3 4 5
```
예상 출력
```
NIE
```
예제 3
입력
```
5
1 1 1 1 1
```
예상 출력
```
3
```
예제 4
입력
```
7
9 99 999 9 999 99 9
```
예상 출력
```
7
```