Un Akaki, n karttan oluşan bir destedir. Her kartın üzerinde 1'den 100000'e kadar tam olarak bir tam sayı vardır. Bazı kartların üzerinde aynı sayıların yazılı olması mümkündür.
Akaki, destedeki tüm kartları sıralamaya karar verdi. Bunu yapmak için sırayla desteden en üstteki bir kartı alır ve üzerinde yazılı olan sayı destedeki kalan tüm sayıların en azına eşitse bu kartı bir kenara koyar. Aksi takdirde, Akaki bu kartı destenin en altına koyar ve destenin tepesinden bir sonraki kartı çeker. Destede hiç kart kalmadığında işlem sona erer. Akaki'nin herhangi bir zamanda destede kalan bazı kartların üzerinde yazan minimum sayıyı bildiğini ancak bu kartın (veya kartların) destede nerede olduğunu bilmediğini varsayabiliriz.
Senin görevin, Akaki'nin destedeki en üstteki karta toplam kaç kez baktığını belirlemek.
Giriş
İlk satırı pozitif bir tamsayı takip eder n (1 ≤ n ≤ 100 000) — destedeki kart sayısı.
İkinci satır, a
1, a
2, ..., a
n ( n pozitif tam sayı dizisini içerir. 1 ≤ a
i ≤ 100 000), burada a
i i'inci üst kartta yazan sayıya eşittir. güverte.< /div>
Çıktı
Akaki'nin destenin en üstündeki kartına toplam bakış sayısını yazdırın.
|
Gir |
Çıktı |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
Not
İlk örnekte, Akaki önce 6 numaralı karta bakacak, destenin en altına koyacak, ardından 3 numaralı kartı da destenin en altına koyacak ve ardından 1 numara. Destede kalan minimum sayıyı içerdiği için 1 numaralı kartı bir kenara koyacaktır. Bundan sonra destedeki kartlar yukarıdan aşağıya [2, 6, 3] şeklinde sıralanacaktır. Bundan sonra Akaki en üstteki 2 numaralı karta bakacak ve onu bir kenara koyacaktır. Bundan sonra, destedeki kartlar yukarıdan aşağıya [6, 3] şeklinde sıralanacaktır. Sonra Akaki 6 numaralı karta bakacak, destenin en altına koyacak ve ardından bir kenara koyacağı 3 numaralı karta bakacak. Bundan sonra destede Akaki'nin bakıp bir kenara bırakacağı 6 numaralı bir kart kalacak. Böylece Akaki 7 karta bakacak.
(c) Kurbatov E., 2018