Дан целочисленный массив $A$ размера $N$. Операция перемешивания (shuffle) определяется следующим образом:

• Изначально создается пустой целочисленный массив $B$.
• Затем, пока $A$ не пуст, вы удаляете либо самый левый, либо самый правый элемент $A$ и добавляете это значение в конец $B$.
• Если $A$ пуст, замените $A$ на $B$ и остановитесь.

Если операция перемешивания выполняется так, как показано на рисунке ниже, значение массива $A$ изменяется следующим образом:

$(34, 19, 5, 36, 4, 25, 12, 9) \to (9, 34, 19, 12, 25, 4, 5, 36)$.

Пусть $A_i$ — $i$-й элемент массива $A$. Говорят, что массив $A$ монотонно возрастает, если выполняется условие: «если $1 \le i < j \le N$, то $A_i \le A_j$».

Напишите программу, которая для заданного целочисленного массива $A$ размера $N$ вычисляет минимальное количество операций перемешивания, необходимых для того, чтобы сделать массив $A$ монотонно возрастающим.

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

В первой строке входных данных содержится целое число $N$ — количество элементов в массиве $A$ ($1 \le N \le 3 \cdot 10^5$). Во второй строке содержатся $N$ целых чисел $A_1, \dots, A_N$: начальные значения элементов массива $A$ ($1 \le A_i \le 10^9$).

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

Выведите минимальное количество операций перемешивания, необходимых для того, чтобы сделать массив $A$ монотонно возрастающим.

Примеры

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

3
2 2 5

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

0

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

6
1 5 8 10 3 2

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

1