#include <bits/stdc++.h>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=1000010;
int n,m,p[N],q[N],f[N],L,R,M,ans,fg;string a,b;
int main(){
	cin>>n>>a>>b;a=" "+a;b=" "+b;
	ref(i,1,n)fg|=(a[i]!=b[i]);
	if(!fg){puts("0");return 0;}
	ref(i,1,n)if(b[i]!=b[i-1])p[++m]=i;
	for(int i=m,j=n;i>0&&j>0;q[i--]=j--)
		while(j>p[i]||j&&a[j]!=b[p[i]])
			f[i]|=(a[j]!=b[p[i]]),j--;
	if(!q[1]){puts("-1");return 0;}q[m+1]=N;
	ref(i,1,m)if(!f[i])q[i]=min(p[i],q[i+1]-1);
	ref(i,1,m){L=i,R=m+1;
		while(L<R)M=(L+R)>>1,(q[M]-M>=p[i]-i)?R=M:L=M+1;
		ans=max(ans,L-i);
	}
	cout<<ans+1<<endl;
}
### Prompt

Please formulate a CPP solution to the following problem:

Shik's job is very boring. At day 0, his boss gives him a string S_0 of length N which consists of only lowercase English letters. In the i-th day after day 0, Shik's job is to copy the string S_{i-1} to a string S_i. We denote the j-th letter of S_i as S_i[j].

Shik is inexperienced in this job. In each day, when he is copying letters one by one from the first letter to the last letter, he would make mistakes. That is, he sometimes accidentally writes down the same letter that he wrote previously instead of the correct one. More specifically, S_i[j] is equal to either S_{i-1}[j] or S_{i}[j-1]. (Note that S_i[1] always equals to S_{i-1}[1].)

You are given the string S_0 and another string T. Please determine the smallest integer i such that S_i could be equal to T. If no such i exists, please print `-1`.

Constraints

* 1 \leq N \leq 1,000,000
* The lengths of S_0 and T are both N.
* Both S_0 and T consist of lowercase English letters.

Input

The input is given from Standard Input in the following format:


N
S_0
T


Output

Print the smallest integer i such that S_i could be equal to T. If no such i exists, print `-1` instead.

Examples

Input

5
abcde
aaacc


Output

2


Input

5
abcde
abcde


Output

0


Input

4
acaa
aaca


Output

2


Input

5
abcde
bbbbb


Output

-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=1000010;
int n,m,p[N],q[N],f[N],L,R,M,ans,fg;string a,b;
int main(){
	cin>>n>>a>>b;a=" "+a;b=" "+b;
	ref(i,1,n)fg|=(a[i]!=b[i]);
	if(!fg){puts("0");return 0;}
	ref(i,1,n)if(b[i]!=b[i-1])p[++m]=i;
	for(int i=m,j=n;i>0&&j>0;q[i--]=j--)
		while(j>p[i]||j&&a[j]!=b[p[i]])
			f[i]|=(a[j]!=b[p[i]]),j--;
	if(!q[1]){puts("-1");return 0;}q[m+1]=N;
	ref(i,1,m)if(!f[i])q[i]=min(p[i],q[i+1]-1);
	ref(i,1,m){L=i,R=m+1;
		while(L<R)M=(L+R)>>1,(q[M]-M>=p[i]-i)?R=M:L=M+1;
		ans=max(ans,L-i);
	}
	cout<<ans+1<<endl;
}
```