B - Flip Digits Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

01 からなる長さ N の文字列 S 及び T が与えられます. あなたは,S に以下の操作を好きな回数行うことができます.

  • S_i=1 となる i (2 \leq i \leq N) を選ぶ. そして,S_i0 で置き換える. さらに,S_{i-1} を今と異なる文字へ変更する.つまり,操作の直前で S_{i-1}0 であれば 1 に,1 であれば 0 に変更する.

ST に一致させることは可能でしょうか? また可能な場合は,そのために必要な最小の操作回数はいくらでしょうか?

制約

  • 1 \leq N \leq 5 \times 10^5
  • S0,1 からなる長さ N の文字列.
  • T0,1 からなる長さ N の文字列.

入力

入力は以下の形式で標準入力から与えられる.

N
S
T

出力

ST に一致させることが可能な場合,必要な最小の操作回数を出力せよ. 不可能な場合,-1 を出力せよ.


入力例 1

3
001
100

出力例 1

2

001 → (i=3 で操作) → 010 → (i=2 で操作) → 100 とすればよいです.


入力例 2

3
001
110

出力例 2

-1

入力例 3

5
10111
01010

出力例 3

5

Score : 600 points

Problem Statement

Given are length-N strings S and T consisting of 0 and 1. You can do the following operation on S any number of times:

  • Choose i (2 \leq i \leq N) such that S_i=1, and replace S_i with 0. Additionally, invert S_{i-1}, that is, change it to 1 if it is 0 now and vice versa.

Is it possible to make S exactly match T? If it is possible, how many operations does it take at least?

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • S is a string of length N consisting of 0 and 1.
  • T is a string of length N consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

N
S
T

Output

If it is possible to make S exactly match T, print the minimum number of operations it takes. Otherwise, print -1.


Sample Input 1

3
001
100

Sample Output 1

2

We can do as follows: 001 → (choose i=3) → 010 → (choose i=2) → 100.


Sample Input 2

3
001
110

Sample Output 2

-1

Sample Input 3

5
10111
01010

Sample Output 3

5