Ëимия готовит фейерверк для фестиваля в Инадзуме. Вокруг неё стоит $n$ столов с компонентами для изготовления фейерверков. На каждом столе стоит ровно один ингредиент.

Сёгун Райдэн попросила сделать самый грандиозный фейерверк в истории, поэтому Ëимия решила смешать все ингредиенты сразу. Но делать это нужно аккуратно, ведь у каждого ингредиента есть уровень опасности – чтобы взрыв не случился раньше времени, на момент добавления в фейерверк нового ингредиента там не должно быть ингредиентов с уровнем опасности выше.

Ингредиенты для фейерверков - очень опасные материалы, поэтому Ëимия может делать с ними всего два действия:

• Переместиться к ингредиенту, который распложен слева или справа от того, около которого стоит Ëимия. Так как ингредиенты расположены по кругу, то, стоя рядом со столом под номером $n$, она может переместиться к $n - 1$-му или первому столу (а стоя у первого - ко второму или к $n$-му).
• Добавить ингредиент, около которого сейчас стоит Ëимия, в фейерверк.

Изначально Ëимия стоит у первого стола. Так как времени очень мало, Ëимия должна сделать фейерверк как можно быстрее. Она хочет знать, какое минимальное количество перемещений между столами с ингредиентами ей нужно сделать, чтобы создать фейерверк.

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

В первой строке записано число $n$ - количество столов с ингредиентами ($1 \le n \le 5 \cdot 10^3$).

Во второй строке через пробел записано $n$ чисел $a_1, a_2, \dots, a_n$, где $a_i$ - уровень опасности ингредиента, стоящего на $i$-том столе ($1 \le a_i \le 10^9$).

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

Выведите одно число – минимально возможное число перемещений между столами, которое может совершить Ëимия во время создания фейрверка.

Подзадачи