사탕

면접 대비

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

요약

정확히 두 종류의 사탕만 포함하는 가장 긴 연속 구간의 사탕 개수를 구합니다.

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

문제

잡화점 주인 보나시에는 사탕을 아주 좋아합니다. 어느 날 저녁 그의 아내 콘스탄스가 사탕 $n$ 개를 한 줄로 늘어놓았습니다. 각 사탕에는 종류 $p_i$ 가 있습니다. 콘스탄스는 남편에게 조건을 하나 걸고 연속된 사탕들을 고르라고 제안했습니다. 고른 구간에는 서로 다른 종류의 사탕이 정확히 두 가지 있어야 합니다. 콘스탄스의 조건을 지키면서 보나시에가 가져갈 수 있는 사탕의 최대 개수를 구해 주세요.

입력

첫 줄에 자연수 $n$ ( $n \le 10^6$ )이 주어집니다. 사탕의 개수입니다. 둘째 줄에는 정수 $p_i$ 가 $n$ 개 주어집니다 ( $1 \le p_i \le 10^9$ ). $p_i$ 는 $i$ 번째 사탕의 종류입니다.

출력

보나시에가 가져갈 수 있는 사탕의 최대 개수를 출력합니다.

힌트

첫 번째 예시에는 종류가 1, 2, 3인 사탕 세 가지가 있습니다. 보나시에는 종류가 3, 3, 1인 처음 세 개의 사탕을 가져갈 수도 있고, 종류가 1, 2, 2, 1인 마지막 네 개의 사탕을 가져갈 수도 있습니다. 따라서 가져갈 수 있는 사탕의 최대 개수는 4입니다.

예제2

예제 1
입력
```
6
3 3 1 2 2 1
```
예상 출력
```
4
```
예제 2
입력
```
2
1 1
```
예상 출력
```
0
```