원형 캠핑장의 빈자리

문제

한 캠핑장에는 원형 산책로를 따라 N개의 야영 구역이 놓여 있다. 구역에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있으며, N번 다음에는 다시 1번이 나온다. 관리인은 함께 온 손님들이 이웃한 구역에 머물 수 있도록, 현재 비어 있는 구역이 가장 길게 이어진 곳을 찾으려 한다. 예약 현황은 길이가 N인 문자열 S로 주어진다. 문자열의 i번째 문자가 마침표 '.'이면 i번 구역이 비어 있고, 샵 '#'이면 이미 예약된 구역이다. 예약된 구역은 새 손님에게 배정할 수 없다. 문자열에는 이 두 종류의 문자만 들어 있으며, 조사하는 동안 예약 현황은 바뀌지 않는다. 관리인이 선택할 수 있는 배정안은 시작 구역 번호와 사용할 구역 수로 정해진다. 시작 구역부터 시계 방향으로 지정한 개수의 구역을 방문했을 때, 방문하는 모든 구역이 비어 있어야 한다. 같은 구역을 두 번 사용할 수 없으므로 사용할 구역 수는 N을 넘을 수 없다. 번호가 N에서 1로 바뀌는 지점은 배정을 끊는 경계가 아니다. 예를 들어 마지막 구역과 첫 구역이 모두 비어 있다면 두 구역을 이어서 사용할 수 있다. 관리인은 사용할 구역 수가 가장 많은 배정안을 선택한다. 최대 개수를 달성하는 시작 구역이 여러 개라면 시작 구역 번호가 가장 작은 배정안을 선택한다. 모든 구역이 비어 있다면 N개 전체를 사용할 수 있으며, 이때도 같은 동점 규칙을 적용한다. 비어 있는 구역이 하나도 없다면 선택 가능한 배정안이 없다고 본다. 문자열 S를 보고 선택한 시작 구역 번호와 사용할 구역 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. 둘째 줄에 길이가 N인 문자열 S가 주어진다.
1 ≤ N ≤ 180,000이다. S의 각 문자는 '.' 또는 '#'이다.

출력

선택한 시작 구역 번호와 사용할 구역 수를 공백으로 구분하여 한 줄에 출력한다. 비어 있는 구역이 없으면 0 0을 출력한다.

8
..##...#

5 3

7
..##...

5 5

3
###

0 0

출처: Devin.KR 자체 제작