Bartek adalah seorang produser musik tekno terkenal, dan saat ini ia sedang menyempurnakan lagu hit berikutnya. Ia telah membuat sebuah trek yang terdiri dari $n$ ketukan (beat), yang diberi nomor secara berurutan dari $1$ hingga $n$. Setelah menghabiskan berjam-jam di program penyunting musik, ia hendak mengekspor berkas mp3, namun ia menyadari bahwa ketukan-ketukan tersebut saat ini tersusun dalam urutan $a_1, a_2, \dots, a_n$. Bartek perlu mendapatkan urutan ketukan yang menaik, yaitu $1, 2, \dots, n$.

Program tersebut mengizinkan dua jenis operasi:

• Memindahkan ketukan terakhir ke posisi mana pun, misalnya $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Memindahkan ketukan mana pun ke paling awal, misalnya $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Berapakah jumlah operasi minimum yang diperlukan untuk menyusun ketukan-ketukan tersebut dalam urutan menaik?

Masukan

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 200\,000$), yang menyatakan jumlah ketukan.

Baris kedua berisi $n$ bilangan bulat yang saling berbeda $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), yang menyatakan urutan ketukan saat ini di dalam program.

Keluaran

Keluarkan satu bilangan bulat – jumlah operasi minimum yang diperlukan.

Contoh

Masukan 1

6
3 2 5 4 1 6

Keluaran 1

4

Masukan 2

9
3 1 2 5 6 4 9 7 8

Keluaran 2

6

Catatan

Kita mulai dengan barisan ketukan $(3, 2, 5, 4, 1, 6)$. Berikut adalah salah satu cara untuk mencapai urutan yang diinginkan dalam empat operasi:

• Pindahkan ketukan terakhir dua posisi ke kiri: $(3, 2, 5, \underline{6}, 4, 1)$.
• Pindahkan ketukan $2$ ke paling awal: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Pindahkan ketukan $1$ ke paling awal: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Pindahkan ketukan terakhir dua posisi ke kiri: $(1, 2, 3, \underline{4}, 5, 6)$.

Urutan menaik dapat diperoleh dengan cara lain menggunakan empat operasi, tetapi tidak dapat dilakukan dalam tiga operasi, sehingga hasilnya adalah $4$.