신을 모시는 사당

면접 대비

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

요약

왼쪽(1)과 오른쪽(2)을 보는 석상이 일렬로 놓여 있을 때, 연속된 구간에서 왼쪽과 오른쪽 개수 차이의 절댓값이 가장 큰 값을 구합니다.

문제

신을 모시는 사당에는 신을 조각한 돌상 $N$ 개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서 있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.

궁극의 깨달음을 얻으려면 금색 돌상들이 가능한 한 많이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 다음과 같이 정의된다.

$|$ (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) $|$

창영이는 궁극의 깨달음을 얻을 수 있을까?

첫째 줄에 돌상의 개수 $N$ 이 주어진다.

둘째 줄에는 돌상이 나열된 순서대로 각 돌상이 바라보는 방향이 주어진다. 입력의 편의상 왼쪽은 1, 오른쪽은 2로 표기한다.

최대한 많은 깨달음을 얻도록 금을 칠했을 때, 얻을 수 있는 깨달음의 양을 출력한다.

$1 \le N \le 100,000$

칠할 수 있는 돌상의 개수에는 제한이 없다. 다만 반드시 연속한(인접한) 돌상만 칠할 수 있으며, 띄엄띄엄 칠할 수는 없다.