Problem
Apabila bermain permainan baharu (beberapa kacukan boling dan biliard), bola N digunakan, bernombor dari 1 hingga N. Pada permulaan permainan, bola ini mesti dibentangkan dalam satu baris dalam susunan berangka. Semasa permainan, pesanan mereka mungkin berubah.
Untuk mengatur bola sebelum permulaan permainan seterusnya, peranti berikut digunakan. Peranti ini terdiri daripada kepala, yang, bergerak di atas bola, boleh "menghisap" dan "memuntahkan" belon. Untuk mendapatkan idea yang lebih baik tentang peranti ini, bayangkan pembersih vakum yang boleh menyedut bola, bergerak ke tempat yang betul, dan di sana, meniup ke arah yang bertentangan, "memuntahkan" bola.
Apabila belon disedut, semua belon yang berada di sebelah kanan belon yang disedut dialihkan ke kiri. "Meludah keluar" bola boleh berada di antara mana-mana dua bola (dan juga sebelum bola pertama atau selepas bola terakhir), kemudian bola meludah dimasukkan di antara bola ini, dan semua bola yang berada di sebelah kanan bola yang dimasukkan dialihkan ke kanan .
Lebih daripada satu bola boleh disedut ke dalam peranti pada masa yang sama, dan apabila meludahkan bola, bola yang disedut terakhir diludahkan dahulu, kemudian bola kedua dari belakang, dan seterusnya. (iaitu peranti berfungsi pada prinsip tindanan). Bola diludah keluar satu demi satu, i.e. anda boleh meludahkan hanya satu bola, meninggalkan selebihnya di dalam peranti (dalam kes ini, anda boleh terus "memuntahkan" bola di tempat yang sama atau di tempat lain, atau menyedut bola baharu).
Operasi yang paling intensif tenaga yang diterangkan ialah operasi menyedut bola, jadi kami mahu meminimumkan bilangan operasi sedemikian sahaja.
Tulis atur cara yang, memandangkan susunan awal bola, akan menentukan bilangan sedutan minimum yang diperlukan untuk menyusun bola dalam susunan berangka.
Input
Dalam fail input, nombor N diberi dahulu — bilangan bola (1≤N≤1000). Kemudian terdapat N nombor yang memberikan nombor bola mengikut urutan dari kiri ke kanan di lokasi semasanya (setiap nombor — dari 1 hingga N dan setiap nombor berlaku tepat sekali dalam urutan).
Output
Keluarkan satu nombor — bilangan minimum operasi menyedut bola yang diperlukan untuk menyusun bola mengikut susunan nombornya.
Ulasan pada ujian sampel
1. Anda boleh menyedut, contohnya, belon nombor 2 dan meludahkannya di antara belon pertama dan ketiga.
2.>Anda boleh melakukan sesuatu seperti ini. Mula-mula,
hisap belon nombor 1, kemudian – bola nombor 2. Kemudian kami bergerak ke permulaan dan meludahkan bola sebelum bola ke-4 (ini akan menjadi bola nombor 2). Seterusnya, sedut belon nombor 3 dan ludahkannya di antara belon 2 dan 4. Kemudian bergerak ke permulaan dan ludahkan belon nombor 1 di sana. Walau bagaimanapun, ini bukan satu-satunya pesanan belon yang mungkin dalam contoh ini.
| Input |
Output |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Olimpik Pasukan, Olimpik Pasukan Moscow, gred 9-11, 2007, Liga A, Masalah F