{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   Choose one lowercase letter $c$. Append $c$ to the end of $S_i$ for all $1 \\leq i \\leq N$.\n*   Choose an integer $i$ such that $1 \\leq i \\leq N-1$. Swap $S_i$ and $S_{i+1}$.\n\nFind 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$.\nWhat 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.\n\n1.  $|S| \\lt |T|$ and $S_1S_2\\ldots S_{|S|} = T_1T_2\\ldots T_{|S|}$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ such that both of the following hold:\n    *   $S_1S_2\\ldots S_{i-1} = T_1T_2\\ldots T_{i-1}$.\n    *   The letter $S_i$ comes before $T_i$ in alphabetical order."},{"iden":"constraints","content":"*   All input values are integers.\n*   $2 \\le N \\le 3 \\times 10^5$\n*   $S_i$ is a string consisting of lowercase English letters.\n*   $1 \\le |S_i|$\n*   $|S_1| + |S_2| + \\dots + |S_N| \\le 3 \\times 10^5$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"5\nab\nrac\na\ndab\nra"},{"iden":"sample output 1","content":"3\n\nHere is one way to operate.\n\n*   Swap $S_2$ and $S_3$. Now $(S_1, \\ldots, S_5) = ($`ab`, `a`, `rac`, `dab`, `ra`$)$.\n*   Append `z` to the end of each string. Now $(S_1, \\ldots, S_5) = ($`abz`, `az`, `racz`, `dabz`, `raz`$)$.\n*   Swap $S_3$ and $S_4$. Now $(S_1, \\ldots, S_5) = ($`abz`, `az`, `dabz`, `racz`, `raz`$)$. At this point, we have $S_i \\leq S_{i+1}$ for all $i = 1, \\ldots, N-1$.\n\nIt is impossible to make $S_i \\leq S_{i+1}$ for all $i = 1, \\ldots, N-1$ with fewer than three operations, so you should print $3$."},{"iden":"sample input 2","content":"3\nkitekuma\nnok\nzkou"},{"iden":"sample output 2","content":"0\n\nBefore any operation is performed, we have $S_i \\leq S_{i+1}$ for all $i = 1, \\ldots, N-1$."},{"iden":"sample input 3","content":"31\narc\narrc\nrc\nrac\na\nrc\naara\nra\ncaac\ncr\ncarr\nrrra\nac\nr\nccr\na\nc\naa\nacc\nrar\nr\nc\nr\na\nr\nrc\na\nr\nrc\ncr\nc"},{"iden":"sample output 3","content":"175\n\nNote that we may have $S_i = S_j$ for $i \\neq j$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}