Задача K1. Любители SMS ≡

Условие

Во время подготовки задач городской олимпиады по информатике отдельные члены жюри пишут остальным много SMS сообщений. Порой размер этих сообщений может исчисляться килобайтами. Естественно, этот процесс был бы очень длительным, если бы не умение указанных членов жюри набирать SMS сообщения за минимально возможное время.

Известно, что члены жюри набирают сообщения с помощью больших пальцев левой и правой рук. Перед набором каждого символа пальцы лежат в центрах двух различных клавиш телефона. Затем один из пальцев перемещается в центр нужной клавиши и нажимает её. Второй палец при этом остаётся на месте.

Время перемещения пальца с одной клавиши на другую составляет d секунд, где d — расстояние между центрами клавиш. Время нажатия на клавишу будем считать пренебрежимо малым.

Расположение клавиш и координаты их центров показаны на приведённой схеме:

  1 2 3   (1; 1) (1; 2) (1; 3)
  4 5 6   (2; 1) (2; 2) (2; 3)
  7 8 9   (3; 1) (3; 2) (3; 3)
    0            (4; 2)
  

Одному члену жюри требуется набрать сообщение, состоящее из N символов. Помогите ему оценить минимальное время, которое для этого потребуется. Клавиша, которую нужно нажать, чтобы ввести i-й символ сообщения, задаётся изображённой на ней цифрой a_i. В начальный момент времени палец левой руки находится на клавише 4, а палец правой руки — на клавише 6.

Рекомендуется рассмотреть частичные решения

• Минимизация расстояния на каждом шаге ведёт к минимизации ответа (жадный алгоритм)
• 1 ≤ N ≤ 20

Формат входного файла

Входной файл содержит целое число N, за которым следуют N цифр a_i.

Формат выходного файла

Выходной файл должен содержать единственное вещественное число t — минимальное время набора сообщения. Абсолютная ошибка ответа не должна превышать 10^− 3.

Ограничения

1 ≤ N ≤ 10⁵, 0 ≤ a_i ≤ 9

Примеры тестов

4
1 3 2 7

5

6
5 2 9 0 0 3

6.650281540