연산 최적화

퍼즐 게임을 좋아하는 현욱이 오늘도 재미있는 퍼즐을 하나 찾아냈다. 플레이어는 빈 문자열 하나를 들고 시작하고, 문자열에 다음 세 가지 연산을 쓸 수 있다.

• A: 현재 문자열의 맨 뒤에 0을 붙인다.
• B: 현재 문자열의 맨 뒤에 1을 붙인다.
• C: 현재 문자열과 똑같은 문자열을 현재 문자열의 맨 뒤에 덧붙인다.

플레이어는 이 연산을 순서대로 이어 붙여 새 연산 $F$를 만들 수 있다. $F$는 사용한 연산을 순서대로 나열해 적는다. 예를 들어 $F = BA$는 주어진 문자열의 맨 뒤에 10을 덧붙이는 연산이다.

퍼즐에는 목표 문자열 $S$가 주어진다. 빈 문자열에 $F$를 두 번 적용한 결과가 $S$와 같아야 한다. 즉 빈 문자열에 $F$를 적용해 얻은 문자열에 $F$를 한 번 더 적용하면 $S$가 나와야 한다.

예를 들어 $S$가 100100이면 $F = BAA$가 조건을 만족한다. 빈 문자열에 $BAA$를 적용하면 100이 되고, 100에 $BAA$를 다시 적용하면 100100이 된다.

$F$의 길이, 즉 $F$에 쓴 연산의 개수가 적을수록 점수가 높다. 현욱을 도와 조건을 만족하는 가장 짧은 $F$의 길이를 구하자.

첫째 줄에 목표 문자열 $S$의 길이 $N$이 주어진다($1 \le N \le 10^6$). 둘째 줄에 목표 문자열 $S$가 주어진다. $S$는 0과 1로만 이루어져 있다.

조건을 만족하는 가장 짧은 $F$의 길이를 출력한다. 그러한 $F$가 없으면 -1을 출력한다.