Problem Statement

You are given $N$ strings $S_1, \dots, S_N$ consisting of lowercase English letters. Consider performing the following two types of operations zero or more times in any order:

• Choose one lowercase letter $c$. Append $c$ to the end of $S_i$ for all $1 \leq i \leq N$.
• Choose an integer $i$ such that $1 \leq i \leq N-1$. Swap $S_i$ and $S_{i+1}$.

Find the minimum total number of operations required to make $S_i \leq S_{i+1}$ in lexicographical order for all $1 \leq i \leq N-1$.

What is lexicographical order? A string $S = S_1S_2\ldots S_{|S|}$ is said to be lexicographically smaller than a string $T = T_1T_2\ldots T_{|T|}$ if 1. or 2. below holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively. $|S| \lt |T|$ and $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$. There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold: $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$. The letter $S_i$ comes before $T_i$ in alphabetical order.

Constraints

• All input values are integers.
• $2 \le N \le 3 \times 10^5$
• $S_i$ is a string consisting of lowercase English letters.
• $1 \le |S_i|$
• $|S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5$

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer in a single line.