U Akaki ialah satu dek daripada n kad. Setiap kad mempunyai tepat satu integer dari 1 hingga 100 000 tertulis padanya. Ada kemungkinan nombor yang sama ditulis pada beberapa kad.
Akaki memutuskan untuk mengisih semua kad di dek. Untuk melakukan ini, dia mengambil secara bergilir-gilir satu kad teratas dari dek dan jika nombor yang ditulis di atasnya adalah sama dengan minimum antara semua nombor yang tinggal dalam dek, dia meletakkan kad ini di tepi. Jika tidak, Akaki meletakkan kad ini di bahagian bawah dek dan menarik kad seterusnya dari bahagian atas dek. Proses ini berakhir apabila tiada kad yang tersisa di dek. Kita boleh mengandaikan bahawa Akaki pada bila-bila masa mengetahui nombor minimum yang ditulis pada beberapa baki kad dalam dek, tetapi tidak tahu di mana kad (atau kad) ini terletak di dek.
Tugas anda ialah untuk menentukan jumlah bilangan kali Akaki melihat kad teratas dari dek.
Input
Baris pertama diikuti oleh integer positif n (1 ≤ n ≤ 100 000) — bilangan kad dalam dek.
Baris kedua mengandungi jujukan n integer positif a
1, a
2, ..., a
n ( 1 ≤ a
i ≤ 100 000), dengan a
i adalah sama dengan nombor yang ditulis pada kad atas ke-i dari dek.< /div>
Output
Cetak jumlah bilangan kali Akaki melihat kad atas dek.
|
Masukkan |
Output |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
Nota
Dalam contoh pertama, Akaki mula-mula akan melihat kad dengan nombor 6, meletakkannya di bahagian bawah dek, kemudian kad dengan nombor 3, juga meletakkannya di bahagian bawah dek, dan kemudian kad dengan nombor 1. Dia akan meletakkan kad dengan nombor 1 di tepi, kerana ia mengandungi nombor minimum daripada baki dalam dek. Selepas itu, kad dalam dek akan terletak dalam susunan [2, 6, 3] dari atas ke bawah. Selepas itu, Akaki akan melihat kad paling atas dengan nombor 2 dan meletakkannya di tepi. Selepas itu, kad dalam dek akan terletak dalam susunan [6, 3] dari atas ke bawah. Kemudian Akaki akan melihat kad nombor 6, letak di bahagian bawah dek, dan kemudian kad nombor 3, yang akan dia ketepikan. Selepas itu, satu kad dengan nombor 6 akan kekal di dek, yang akan Akaki lihat dan ketepikan. Oleh itu, Akaki akan melihat 7 kad.
(c) Kurbatov E., 2018