Diberikan sebuah larik bilangan bulat $A$ berukuran $N$, operasi pengacakan didefinisikan sebagai berikut.

• Awalnya, buat sebuah larik bilangan bulat kosong $B$.
• Kemudian, selama $A$ tidak kosong, hapus elemen paling kiri atau paling kanan dari $A$, lalu tambahkan nilainya di sebelah kanan dalam $B$.
• Jika $A$ kosong, ganti $A$ dengan $B$ dan berhenti.

Jika operasi pengacakan dilakukan seperti pada gambar di atas, nilai larik $A$ berubah sebagai berikut:

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

Misalkan $A_i$ adalah elemen ke-$i$ dari larik $A$. Jika syarat “jika $1 \le i < j \le N$, maka $A_i \le A_j$” terpenuhi, larik $A$ dikatakan menaik secara monoton.

Tulislah program yang, untuk sebuah larik bilangan bulat $A$ berukuran $N$, menghitung banyaknya minimum operasi pengacakan yang diperlukan untuk membuat larik $A$ menaik secara monoton.

Masukan

Baris pertama masukan berisi satu bilangan bulat $N$, yaitu banyaknya elemen dalam larik $A$ ($1 \le N \le 3 \cdot 10^5$).

Baris kedua berisi $N$ bilangan bulat $A_1,\ldots,A_N$: nilai awal elemen-elemen larik $A$ ($1 \le A_i \le 10^9$).

Keluaran

Keluarkan banyaknya minimum operasi pengacakan yang diperlukan untuk membuat larik $A$ menaik secara monoton.

Contoh

Masukan 1

3
2 2 5

Keluaran 1

0

Masukan 2

6
1 5 8 10 3 2

Keluaran 2

1