Limonad cərgəsi
Bu gün fermada isti yay günüdür və Fermer Con öz n inəyinə limonad paylayır. Bütün n inək (ardıcıl olaraq 1..n nömrələnmiş) limonadı sevir, amma bəziləri digərlərindən daha çox sevir. Xüsusilə, i inəyi limonadını almadan əvvəl ən çox w[i] inək gözləməyə hazırdır. Hal-hazırda bütün n inək sahələrdədir, lakin tezliklə FC zəngi çalacaq və inəklər ona doğru qaçacaq. O, limonadı paylamağa başlamazdan əvvəl hamısı gələcək, lakin heç bir iki inək eyni vaxtda gəlməyəcək. Üstəlik, i inəyi gələndə yalnız o halda növbəyə durur ki, növbədə ən çox w[i] inək olsun.
FC əvvəlcədən müəyyən miqdarda limonad hazırlamaq istəyir, lakin israf etmək istəmir. Növbəyə duran inəklərin sayı onların gəlmə sırasından asılıdır. Ona inəklərin növbəyə dura biləcəyi minimal sayını müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) ədədini, ikinci sətir isə w[1], w[2], .., w[n] tam ədədlərini ehtiva edir. Hər bir i inəyi üçün 0 ≤ w[i] ≤ 10^9 təmin edilir.
Çıxış Məlumatları
İnəklərin gəlmə sıralarının hamısı arasında növbəyə dura biləcək minimal inək sayını çıxarın.
Nümunə
Bu halda yalnız 3 inək növbəyə dura bilər (bu, mümkün olan minimal sayıdır). w = 7 və w = 400 olan inəklər əvvəlcə gəlib növbəyə dursun. Sonra w = 1 olan inək gələcək - və gedəcək, çünki artıq iki inək növbədədir. Sonra w = 2 olan iki inək gələcək, biri növbəyə duracaq, digəri gedəcək.