King of String Comparison#13020

King of String Comparison

1 second
256 megabytes
Medium

You are given two strings of length . 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 is lexicographically smaller than a string if and only if one of the following holds:

Input

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

The second and the third lines of the input contain strings , of length 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

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Example 5

Loading
Loading

Note

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