영화관

Axel과 Beatrice는 함께 영화를 보러 간다. 두 사람은 같은 줄에, 가능하면 서로 바로 옆에 앉고 싶어 한다. 서로 바로 옆인 빈 좌석 두 개가 없다면 가능한 한 서로 가까운 좌석 두 개를 원한다.

앉기에 가장 좋은 줄을 찾기 위해 두 사람은 당신에게 도움을 청한다. 특정 줄에서 어떤 좌석이 비어 있는지에 대한 설명이 주어질 때, 빈 좌석 두 개 사이의 최단 거리를 구한다. 거리는 두 빈 좌석 사이에 있는 좌석의 수이다.

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$60$| $1 \le N \le 1\,000$

$2$ |$40$| $1 \le N \le 1\,000\,000$

첫째 줄에는 살펴볼 줄의 좌석 수를 나타내는 정수 $1 \le N \le 1\,000\,000$이 주어진다.

둘째 줄에는 $N$개의 문자로 이루어진 문자열이 주어진다. 이 문자열의 $i$번째 문자는 줄의 $i$번째 좌석이 사용 중이면 '#', 좌석이 비어 있으면 '.'이다. 적어도 두 좌석이 비어 있음, 즉 적어도 두 문자가 '.'임이 보장된다.

빈 좌석 두 개 사이의 최단 거리를 나타내는 정수를 출력한다.