Six-Digit Documents

Valery, an accountant, is checking inconsistencies in accounting reports. He has to check exactly $n$ documents. The $i$-th document is available on the corporate network by its six-digit integer identifier $a\_i$.

An inversion in the $k$-th digit is a pair of indices $i$ and $j$ such that $i < j$ and the $k$-th digit of $a\_i$ is strictly greater than the $k$-th digit of $a\_j$. The complexity of an array of six-digit numbers $\{a\_i\}$ is the total number of inversions across all six digit positions.

Valery knows that the lower the complexity of the identifiers, the less time he spends typing them into the address bar. The set of documents is fixed, and reordering them freely is risky because he might skip some documents by mistake. The only change he is allowed to make is to shift the order cyclically by several positions. A cyclic shift of the array $a\_1, a\_2, \ldots, a\_n$ by $t$ positions to the left is the array $a\_{t+1}, a\_{t+2}, \ldots, a\_n, a\_1, a\_2, \ldots, a\_t$.

Help Valery choose the cyclic shift of the original array with the minimum complexity.

The first line contains an integer $n$, the number of documents to check ($1 \leqslant n \leqslant 100\,000$). Each of the next $n$ lines contains six digits, the identifier $a\_i$. All $a\_i$ are distinct. Identifiers may start with zero.

Print a single integer: the minimum complexity over all cyclic shifts of the array of identifiers.

In the first sample, it pays to shift one position to the left, so the number 177013 comes first. Then each of the first four digit positions has one inversion, and the last two have none.

In the second sample, the order is already optimal with three inversions: one each in the first, fourth, and sixth digit positions.