409095: GYM103438 A King of String Comparison

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$$$.

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 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$$$.

3
aab
aba

4

4
icpc
cool

4

4
zyzz
life

0

7
trivial
problem

16

18
goodluckandhavefun
letthestrongestwin

112

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