Для масиву цілих чисел $A$ розміру $N$ операція перемішування визначається так:

• Спочатку створіть порожній масив цілих чисел $B$.
• Потім, поки $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$. Коли виконується умова «якщо $1 \le i < j \le N$, то $A_i \le A_j$», кажуть, що масив $A$ монотонно зростає.

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

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $N$ — кількість елементів масиву $A$ ($1 \le N \le 3\cdot10^5$).

Другий рядок містить $N$ цілих чисел $A_1,\ldots,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