Farmer John хочет фото всего стада $N$, $1 \le N \le 100,000$, номера $1..N$, чтобы похвастаться друзьям.

В день фотографии коровы бегут и выстраиваются в произвольную линию, позиция $i$ содержит $c_{i}$, $1 \le c_{i} \le N$. У него свои идеи порядка.

По мнению FJ, Корова $i$ может стоять только слева от $i+1$ для всех $i$, $1 \le i \le N-1$, а $N$ только слева от $1$. Конечно, слева от первой, крайней левой, никто не стоит.

Коровы голодны, ждут обещанный ужин после фото, поэтому он спешит. Они плохо слушаются: можно раз в минуту выбрать соседнюю пару и обменять местами. Как быстро получить допустимый порядок?

Пример пяти коров вначале:

     Слева           Справа
        3  5  4  2  1

Сначала обменять вторую пару:

        3  4  5  2 1

Потом крайнюю правую:

        3  4  5  1  2

Получится допустимый порядок всего за две минуты обменов.

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

• Строка $1$: одно целое $N$.

• Строки $2..N+1$: строка $i+1$, номер $i$-й коровы $c_{i}$.

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

• Строка $1$: минимальное время в минутах для подходящего порядка.

Примеры

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

5
3
5
4
2
1

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

2

Примечание

Автор задачи: Travis, 2010