F. 4-красота
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для множества целых чисел $$$S$$$ определим его характеристику делимости как количество упорядоченных пар $$$(x, y)$$$ таких, что $$$x \ne y$$$, $$$x$$$ и $$$y$$$ принадлежат $$$S$$$, и $$$x$$$ делится на $$$y$$$.

Для множества целых чисел $$$A$$$ определим его $$$4$$$-красоту следующим образом:

  • рассмотрим все множества из четырёх различных чисел, принадлежащих $$$A$$$ и образующих арифметическую прогрессию;
  • найдем максимум из характеристик делимости среди всех таких множеств.

Если подходящих множеств из четырёх чисел нет, то $$$4$$$-красота равна $$$0$$$.

Изначально дано множество $$$\{1, 2, \ldots, n\}$$$. Вы можете удалять из него числа. За удаление числа $$$i$$$ необходимо заплатить $$$m_i$$$ монет.

Найдите минимальное количество монет, которое нужно заплатить, чтобы уменьшить $$$4$$$-красоту множества.

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

В первой строке задано целое число $$$n$$$ ($$$4 \le n \le 5 \cdot 10^5$$$) — количество чисел в исходном множестве.

Во второй строке заданы $$$n$$$ целых чисел $$$m_1, m_2, \ldots, m_n$$$ ($$$1 \le m_i \le 10^9$$$), где $$$m_i$$$ — стоимость удаления числа $$$i$$$.

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

Выведите одно целое число — минимальное количество монет, которое нужно заплатить, чтобы уменьшить $$$4$$$-красоту множества. Можно показать, что в ограничениях задачи это всегда возможно.

Примеры
Входные данные
4
5 3 7 2
Выходные данные
2
Входные данные
5
1 100 100 100 1
Выходные данные
1
Входные данные
8
2 10 100 10 100 3 100 100
Выходные данные
5
Входные данные
10
9 9 7 4 8 2 6 5 1 10
Выходные данные
4
Примечание

В первом примере единственная арифметическая прогрессия из четырёх чисел — $$$1, 2, 3, 4$$$. Её характеристика делимости равна $$$4$$$. Достаточно удалить число $$$4$$$, заплатив $$$2$$$ монеты.

Во втором примере достаточно удалить число $$$1$$$.

В третьем примере оптимально удалить числа $$$1$$$ и $$$6$$$, заплатив $$$2+3=5$$$ монет.