AlanashKO menyukai uang. Menjelang Tahun Baru, ia diberi $N$ lembar uang kertas. Nilai nominal setiap lembar adalah bilangan bulat positif. Saat bermain, AlanashKO menyusun semua uang kertas dalam satu baris dan menomorinya dari kiri ke kanan, dari $1$ sampai $N$. Kemudian ia memutuskan untuk mengurutkan semua uang kertas dalam urutan tidak menurun.

Untuk itu, AlanashKO melakukan prosedur berikut. Pertama, ia membagi uang kertas menjadi satu atau lebih subsegmen yang saling lepas, sehingga setiap lembar termasuk dalam suatu subsegmen. Kemudian, semua subsegmen secara bergiliran dimasukkan ke baris baru menurut urutan dari kiri ke kanan: mula-mula subsegmen paling kiri (subsegmen pertama), lalu subsegmen berikutnya dari kiri, dan seterusnya. Setiap subsegmen dimasukkan di antara dua lembar uang kertas mana pun atau pada salah satu dari kedua ujung baris baru saat itu. Urutan uang kertas di dalam subsegmen tidak berubah saat dimasukkan.

AlanashKO ingin meminimalkan banyaknya subsegmen agar pada akhirnya ia dapat mengurutkan uang kertas dalam urutan tidak menurun. Bantulah ia menentukan nilai tersebut.

Masukan

Baris pertama berisi satu bilangan bulat positif $N$ ($1 \le N \le 10^6$), yaitu banyaknya uang kertas. Baris berikutnya berisi $N$ bilangan bulat positif $a_i$ ($1 \le a_i \le 10^6$), yaitu nilai nominal lembar uang kertas ke-$i$.

Keluaran

Cetak satu bilangan bulat pada satu baris: banyaknya subsegmen minimum yang memungkinkan AlanashKO mengurutkan uang kertas.

Penilaian

Soal ini mencakup empat subsoal:

1. $N \le 8$. Bernilai 9 poin.
2. $N \le 20$. Bernilai 16 poin.
3. $N \le 300$. Bernilai 20 poin.
4. $N \le 10^6$. Bernilai 55 poin.

Suatu subsoal hanya akan diberi nilai jika solusi berhasil melewati semua subsoal sebelumnya.

Contoh

Masukan 1

6
3 6 4 5 1 2

Keluaran 1

3

Catatan

Subsegmen adalah urutan elemen yang berurutan.

Mari kita tinjau contoh pengujian:

Jawaban minimum adalah pembagian menjadi 3 subsegmen: |3 6|4 5|1 2| (garis tegak menandai batas subsegmen).

Setelah langkah pertama: baris awal adalah |4 5|1 2|, baris baru adalah |3 6|.

Pada langkah kedua, subsegmen |4 5| dimasukkan di antara $3$ dan $6$.

Setelah langkah kedua: baris awal adalah |1 2|, baris baru adalah |3 4 5 6|.

Kemudian, subsegmen |1 2| dimasukkan di awal baris baru, sehingga hasilnya adalah |1 2 3 4 5 6|.