Minimized Concatenated String Length

Little Blue has made \(n\) workpieces. Each workpiece is represented by a string of length 2 composed of lowercase English letters, denoted by \(s_i\) for \(1 \le i \le n\). He wants to concatenate the workpieces in the given order to form a string \(S = s_1 + s_2 + \ldots + s_n\). The concatenation operator \(+\) works in a peculiar way: when concatenating two strings \(a\) and \(b\) (each initially of length 2), if the second character of \(a\) equals the first character of \(b\), then the resulting string \(c = a+b\) has length 3 rather than 4 (i.e. the common character is not duplicated). For example, xy + yz = xyz while xy + zy = xyzy.

Before concatenation, Little Blue is allowed to reverse any workpiece (i.e. change a string \(xy\) to \(yx\)). Note that the workpieces must be concatenated in their original order, though each can be individually flipped. Determine the minimum possible length of the concatenated string \(S\) after optimally deciding which pieces to reverse.

The final length can be calculated as follows. If no overlapping occurs, the total length is \(2n\) (since every piece contributes 2 characters) and every successful overlap reduces the length by 1. Thus, if the maximum number of overlaps is \(\ell\), the answer is \(2n - \ell\).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of workpieces. The following \(n\) lines each contain a string of length 2 consisting of lowercase English letters representing the workpieces.

outputFormat

Output a single integer, the minimum possible length of the concatenated string after optimally flipping some pieces.

sample

3
xy
yz
zx

4