이변 마작 9

면접 대비

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

요약

최대 100000개의 패에서 같은 종류가 5개 들어 있는 가장 짧은 연속 구간의 길이를 구합니다. 그런 구간이 없으면 -1을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 해시맵, 배열
정답자: 아직 제출이 없습니다

문제

마작의 패(牌)는 34종류의 패가 각각 4장씩, 총 136장으로 이루어져 있습니다. 패의 종류는 다음과 같습니다.

이름	설명
만수패(萬數牌)	한자가 쓰여 있는 패입니다. `1m`, `2m`, `3m`, `4m`, `5m`, `6m`, `7m`, `8m`, `9m`으로 총 9개의 종류가 있습니다.
통수패(筒數牌)	바퀴가 그려진 패입니다. 바퀴의 개수에 따라 `1p`, `2p`, `3p`, `4p`, `5p`, `6p`, `7p`, `8p`, `9p`로 총 9개의 종류가 있습니다.
삭수패(索數牌)	대나무가 그려진 패입니다. 대나무의 개수에 따라 `1s`, `2s`, `3s`, `4s`, `5s`, `6s`, `7s`, `8s`, `9s`로 총 9개의 종류가 있습니다.
자패(字牌)	글자가 쓰여 있는 패입니다. `1z`, `2z`, `3z`, `4z`, `5z`, `6z`, `7z`로 총 7개의 종류가 있습니다.

여러분은 패를 섞어서 하나씩 놓아보고 있었습니다. 그러던 도중 패의 종류가 바뀌는 이변이 일어났습니다. 같은 종류의 패가 4장씩 있다는 사실을 알고 있던 여러분은 이변을 해결했습니다.

이번에는 더 큰 이변이 일어나고 있습니다. 패의 종류가 바뀐 것에 더해, 패가 늘어나 최대 $100\,000$ 장의 패가 쌓이게 되었습니다. 여러분은 늘어난 패의 개수에서 이상함을 눈치채지 못했습니다. 그래서 이전과 같이 같은 종류의 패가 5장 이상 나오는지 확인해야 합니다. 여러분의 기억력 $X$ 는 유한하기 때문에 가장 최근에 놓은 $X$ 장의 패만 기억할 수 있습니다. 즉, 이변을 눈치채려면 어떤 패를 놓은 직후에 기억 속의 $X$ 장 중 같은 종류의 패가 5장 이상 있어야 합니다.

이변을 눈치채기 위해 필요한 최소 기억력을 구해 주세요. 아무리 기억력이 좋아도 이변을 눈치챌 수 없다면 -1을 출력합니다.

입력

첫 번째 줄에 놓을 패의 개수 $N$ 이 주어집니다. $(1 \le N \le 100\,000)$

두 번째 줄에 놓아볼 순서대로 $N$ 장의 패의 종류가 공백으로 구분되어 주어집니다. 입력으로 주어지는 모든 패는 위에서 설명한 34종 중 하나입니다.

출력

이변을 눈치채기 위해 필요한 최소 기억력을 출력합니다. 아무리 기억력이 좋아도 이변을 눈치챌 수 없다면 -1을 출력합니다.

예제2

예제 1
입력
```
9
5z 2z 5z 5z 5z 6z 5z 5z 3z
```
예상 출력
```
6
```

예제 2

입력

13
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m

예상 출력

-1