Naman has two binary strings $s$ and $t$ of length $n$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $s$ into $t$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $s$ and rotate it clockwise once.

For example, if $s = 1\textbf{1}101\textbf{00}$, he can choose a subsequence corresponding to indices ($1$-based) $\{2, 6, 7 \}$ and rotate them clockwise. The resulting string would then be $s = 1\textbf{0}101\textbf{10}$.

A string $a$ is said to be a subsequence of string $b$ if $a$ can be obtained from $b$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $c$ of size $k$ is to perform an operation which sets $c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $s$ into $t$ or say that it is impossible. 


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^6)$ — the length of the strings.

The second line contains the binary string $s$ of length $n$.

The third line contains the binary string $t$ of length $n$.


-----Output-----

If it is impossible to convert $s$ to $t$ after any number of operations, print $-1$.

Otherwise, print the minimum number of operations required.


-----Examples-----
Input
6
010000
000001

Output
1
Input
10
1111100000
0000011111

Output
5
Input
8
10101010
01010101

Output
1
Input
10
1111100000
1111100001

Output
-1


-----Note-----

In the first test, Naman can choose the subsequence corresponding to indices $\{2, 6\}$ and rotate it once to convert $s$ into $t$.

In the second test, he can rotate the subsequence corresponding to all indices $5$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $s$ into $t$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = input()
t = input()

curr = 0
currs = []
for i in range(n):
    if s[i] == '1':
        curr += 1
    if t[i] == '1':
        curr -= 1
    currs.append(curr)

if curr != 0:
    print(-1)
else:
    print(max(currs)-min(currs))


n = int(input())
s = input()
t = input()
if s.count('1') != t.count('1'):
    print(-1)
    return

p = []
ans = [0, 0]
for i in range(n):
    if s[i] != t[i]:
        if p and s[i] != p[-1]:
            p.pop(-1)
        else:
            p.append(s[i])
            w = int(s[i])
            ans[w] = max(ans[w], len(p))
print(sum(ans))

n = int(input())
a = input()
b = input()
diff = 0
maxDiff = 0
minDiff = 0
for i in range(n):
    if a[i] == '1':
        diff += 1
    if b[i] == '1':
        diff -= 1
    if diff > maxDiff:
        maxDiff = diff
    if diff < minDiff:
        minDiff = diff
if diff != 0:
    print(-1)
else:
    print(maxDiff - minDiff)


import sys
n = int(input())

s = input()
t = input()

ssum = 0
tsum = 0
for i in range(n):
    ssum += int(s[i])
    tsum += int(t[i])

if ssum != tsum:
    print (-1)
    return

nex = [0,0]

for i in range(n):

    if s[i] == "0" and t[i] == "1":

        if nex[1] > 0:
            nex[1] -= 1
            nex[0] += 1
        else:
            nex[0] += 1

    if s[i] == "1" and t[i] == "0":

        if nex[0] > 0:
            nex[0] -= 1
            nex[1] += 1
        else:
            nex[1] += 1

print (sum(nex))

n = int(input())
s = input()
t = input()
if(sorted(s)!=sorted(t)):
	print(-1)
	return
s1 = 0
s2 = 0
ans1 = 0
ans2 = 0
for i in range(len(s)):
	if(s[i]!=t[i]):
		if(s[i]=='0'):
			#a01
			if(s2>0):
				s2 -= 1
			else:
				s1 += 1
				ans1 = max(ans1, s1)
		else:
			#a10
			if(s1>0):
				s1 -= 1
			else:
				s2 += 1
				ans2 = max(ans2, s2)
print(ans1 + ans2)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
s = list(input().rstrip())
t = list(input().rstrip())

if s.count("1") != t.count("1"):
    print(-1)
    return

ns = []
for si, ti in zip(s, t):
    if si != ti:
        ns.append(si)
ns = ns + ns
d = 0
ans = 0
for item in ns:
    if item == "1":
        d += 1
    else:
        d -= 1
        if d < 0:
            d = 0
    ans = max(ans, d)

print(ans)

input()
s0=input()
s1=input()
if s0.count('1')!=s1.count('1'):
	print(-1)
else:
	m0=0
	m1=0
	v0=0
	v1=0
	for i,j in zip(s0,s1):
		if i!=j:
			v0+= 1 if i=='1' else -1
			v1+= 1 if j=='1' else -1
			m0=max(v0,m0)
			m1=max(v1,m1)
	print(m0+m1)