Восстановление массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
recovery.in
вывод
recovery.out

Кэти подарила Максу массив неубывающих чисел на день рождения. Он безумно ему понравился, однако друзья решили пошутить и добавили несколько цифр в некоторых числах массива, пока Макса не было рядом. Наш герой сразу заметил, что что-то не так — массив перестал быть неубывающим! Он впал в отчаяние, но на помощь ему пришла Гиджет — она сказала, что поможет ему восстановить массив.

Гиджет знает, что исходный массив возможно получить уже не получится, потому что его никто не помнит, но можно хотя бы попробовать восстановить свойство неубывания элементов, удаляя некоторые цифры из элементов массива. Конечно, изменять количество элементов массива не стоит — Макс сразу это заметит, поэтому удалять все цифры из какого-либо числа она не хочет. Так как Макс в полном отчаянии и времени у нее не так много, она хочет восстановить свойства исходного массива, удалив наименьшее количество цифр. Помогите ей с этой непростой задачей!

Входные данные

В первой строке входного файла дано число n — количество элементов массива (1 ≤ n ≤ 1000).

В следующих n строках даны элементы массива — целые неотрицательные числа ai. Гарантируется, что числа в массиве не содержат нулей и суммарная длина всех чисел в массиве не превосходит 100 000.

Выходные данные

В единственной строке выходного файла выведите минимальное количество цифр, которое надо удалить, чтобы элементы массива снова стали неубывающими.

Если не существует способа удалить несколько цифр так, чтобы в получившемся массиве числе неубывали, в единственной строке выходного файла выведите «-1».

Примеры

Входные данные
4
93
31
23
31
Выходные данные
2
Входные данные
4
93
31
23
12
Выходные данные
3
Входные данные
4
93
31
23
2
Выходные данные
-1

Примечание

В первом примере достаточно удалить первую цифру первого числа и вторую цифру второго, получится последовательность 3, 3, 23, 31, которая является неубывающей.

Во втором примере также нужно удалить первую цифру третьего числа, чтобы получить последовательность 3, 3, 3, 12.