A. King of String Comparison
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two strings $$$s, t$$$ of length $$$n$$$. Find the number of pairs $$$(l, r)$$$ of integers such that $$$1 \le l \le r \le n$$$ and the substring $$$s_ls_{l+1}s_{l+2}\ldots s_r$$$ is lexicographically smaller than $$$t_lt_{l+1}t_{l+2}\ldots t_r$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$).

The second and the third lines of the input contain strings $$$s$$$, $$$t$$$ of length $$$n$$$ correspondingly, each consisting only of lowercase Latin letters.

Output

Output a single integer — the number of pairs $$$(l, r)$$$ of integers such that $$$1 \le l \le r \le n$$$ and the substring $$$s_ls_{l+1}s_{l+2}\ldots s_r$$$ is lexicographically smaller than $$$t_lt_{l+1}t_{l+2}\ldots t_r$$$.

Examples
Input
3
aab
aba
Output
4
Input
4
icpc
cool
Output
4
Input
4
zyzz
life
Output
0
Input
7
trivial
problem
Output
16
Input
18
goodluckandhavefun
letthestrongestwin
Output
112
Note

In the first sample, there are $$$4$$$ such pairs: $$$(1, 2), (1, 3), (2, 2), (2, 3)$$$.