시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 221 63 54 36.735%

문제

서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 있고, 꺼져있을 수도 있다.

상근이는 이 전구를 조작하기 위해서, 집에서 전구를 조작하는 기계를 가지고 왔다. 이 기계는 어떤 구간의 전구를 지정하면, 불이 켜있는 전구의 불을 끄고, 꺼져있는 전구의 불을 켜는 기능이 있다. 하지만, 이 기계는 상당히 오래된 기계로, 한 번 사용하면 다음 해까지 더 이상 사용할 수 없다.

서강대학교 학생들은 불이 켜있는 전구와 꺼져있는 전구가 번갈아가면서 나타나는 패턴을 좋아한다. 이러한 패턴을 교대 패턴이라고 한다. 따라서, 상근이는 이 기대를 1번만 사용해서 가장 긴 교대 패턴을 만들기로 했다.

예를 들어, 전구가 아래와 같이 배열되어 있다고 하자. (○는 불이 들어와 있는 전구, ●는 꺼져있는 전구)

○ ○ ● ● ○ ● ○ ○ ○ ●

4번째부터 7번째까지 4개 전구에 기계를 사용하면 아래와 같이 된다.

○ ○ ● ○ ● ○ ● ○ ○ ●

위의 경웅에는 2번째부터 8번째까지 전구가 길이가 7인 교대 패턴을 이룬다.

또, 8번째 전구에만 기계를 조작하면 아래와 같이 된다.

○ ○ ● ● ○ ● ○ ● ○ ●

이렇게 되면, 4번째부터 10번째까지 전구가 길이가 7인 교대 패턴을 만든다.

즉, 기계를 최대 한 번만 사용해서 길이가 8 이상인 교대 패턴을 만들 수 없다.

전구의 정보가 주어졌을 때, 기계를 최대 한 번 사용해서 얻을 수 있는 가장 긴 교대 패턴의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 전구의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)

두번째 줄에는 전구의 상태가 왼쪽 전구부터 순서대로 주어진다. 전구의 상태는 1 또는 0이며, 1은 불이 켜져있는 상태, 0은 불이 꺼져있는 상태이다.

출력

첫째 줄에 상근이가 기계를 최대 한 번 사용해서 얻을 수 있는 가장 긴 교대 패턴의 길이를 출력한다.

예제 입력

10
1 1 0 0 1 0 1 1 1 0

예제 출력

7

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2013 1번