Operation Optimization

Time limit2sMemory limit256 MB

Summary

Find the shortest sequence of append-0, append-1, and self-doubling operations whose two-fold application to the empty string yields a given binary string S.

Level: Hard8 of 10
Topics: String, Greedy, Math, Implementation
Solved: No attempts yet

Problem

Hyunwook, who loves puzzle games, has found another interesting puzzle. The player starts with one empty string and can apply the following three operations to it.

A: append 0 to the end of the current string.
B: append 1 to the end of the current string.
C: append a copy of the current string to the end of the current string.

The player can chain these operations in order to form a new operation $F$ . $F$ is written as the list of the operations used, in order. For example, $F = BA$ is the operation that appends 10 to the end of the given string.

The puzzle gives a target string $S$ . Applying $F$ twice to the empty string must produce $S$ . That is, applying $F$ to the empty string gives some string, and applying $F$ once more to that string must give $S$ .

For example, if $S$ is 100100, then $F = BAA$ satisfies the condition. Applying $BAA$ to the empty string gives 100, and applying $BAA$ to 100 gives 100100.

The shorter $F$ is, that is, the fewer operations $F$ uses, the higher the score. Help Hyunwook find the length of the shortest $F$ that satisfies the condition.

Input

The first line contains the length $N$ of the target string $S$ ( $1 \le N \le 10^6$ ). The second line contains the target string $S$ . $S$ consists only of 0 and 1.

Output

Print the length of the shortest $F$ that satisfies the condition. If no such $F$ exists, print -1.

Examples2

Example 1
Input
```
6
100100
```
Expected output
```
3
```
Example 2
Input
```
1
1
```
Expected output
```
-1
```