두 차량의 대기 칸

문제

한 주차장에는 1번부터 N번까지 번호가 붙은 주차 칸이 있다. 각 칸에는 차량이 정확히 한 대 주차되어 있거나 아무 차량도 없다. 관리 장치는 현재 주차된 차량 중 서로 다른 두 대를 골라 동시에 출차시키려 한다. 두 차량을 고르는 순서는 구별하지 않는다. 이 주차장의 출차 장치는 주차 칸의 번호를 이용해 임시 대기 칸을 정한다. 선택한 차량이 있는 칸의 번호가 a와 b라면, 임시 대기 칸의 번호는 a와 b의 최대공약수인 gcd(a,b)가 된다. 최대공약수는 두 양의 정수를 모두 나누는 가장 큰 양의 정수다. 장치의 안전 규칙에 따라 임시 대기 칸은 두 차량을 선택하기 직전부터 비어 있어야 한다. 따라서 임시 대기 칸에 선택한 차량 중 한 대가 주차되어 있는 경우에도 그 두 차량은 함께 출차할 수 없다. 관리자는 현재 상태에서 함께 출차할 수 있는 차량 쌍의 총개수를 알고 싶다. 또한 비어 있는 각 칸에 대해, 그 칸을 임시 대기 칸으로 사용하는 차량 쌍의 개수를 비교하려 한다. 함께 출차할 수 있는 차량 쌍이 하나 이상이면 가장 많은 쌍이 사용하는 임시 대기 칸의 번호와 그 쌍의 개수도 구해야 한다. 가장 많은 쌍이 사용하는 빈 칸이 여러 개면 번호가 가장 작은 칸을 고른다. 모든 차량 쌍은 입력으로 주어진 동일한 주차 상태에서 독립적으로 판단한다. 실제로 차량을 이동하거나 출차시켜 다른 쌍을 판단할 때의 상태를 바꾸지 않는다. 함께 출차할 수 있는 차량 쌍이 하나도 없으면 총개수는 0이며, 선택할 임시 대기 칸이 없음을 나타내는 정해진 값을 출력한다.

입력

첫째 줄에 주차 칸의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어지며, 왼쪽에서 i번째 문자가 1이면 i번 칸에 차량이 주차되어 있고 0이면 비어 있다. 차량이 한 대도 없는 상태도 입력으로 주어질 수 있다.

출력

첫째 줄에 함께 출차할 수 있는 순서 없는 차량 쌍의 총개수를 정수로 출력한다. 총개수가 양수이면 둘째 줄에 가장 많은 쌍이 사용하는 빈 임시 대기 칸의 번호와 그 쌍의 개수를 공백으로 구분하여 출력한다. 동점이면 칸 번호가 가장 작은 것을 출력한다. 총개수가 0이면 둘째 줄에 -1 0을 출력한다.

8
01110101

3
1 3

12
000001000101

2
2 2

6
110100

0
-1 0

출처: Devin.KR 자체 제작