Qüllələr#8566
Şəhər X qərbdən şərqə doğru düz bir xətt boyunca yerləşən və 1-dən n-ə qədər nömrələnmiş n binadan ibarətdir. Hər bir bina fərqli hündürlüyə malikdir: h[1], h[2], ..., h[n]. Şəhər hökuməti bu binaların sırasına uyğun olaraq bir qüllə tikməyi planlaşdırır (bu, birinci binadan əvvəl, iki bina arasında və ya son binadan sonra ola bilər). Qüllə vətəndaşlara mesajlar ötürəcək. Qüllənin hündürlüyü H olmalıdır və bu hündürlük bütün binaların hündürlüyündən fərqli olmalıdır.
Texniki səbəblərə görə, qüllə yalnız qərbə (binaların sırasının başlanğıcına) siqnallar ötürə bilir. Siqnallar üfüqi hərəkət edən (torpaqla paralel olan) şüalardır və qüllənin bütün səthindən (yuxarıdan aşağıya) yayılır. Bu səbəbdən, qüllə hündürlüyünə bərabər olan bir enlikdə davamlı siqnal zolağı yayır. Şüa binaya dəydikdə dayanır. Hər bina siqnalları zirvəsində yerləşən qəbuledici vasitəsilə qəbul edir. Bina mesaj alırsa, ən azı bir şüa onun qəbuledicisinə çatır.
Başqa sözlə, i nömrəli bina qüllədən mesaj alacaq, əgər: bina i qüllənin qərbində yerləşirsə; i qüllədən hündür deyilsə; və onların arasında j nömrəli başqa bir bina (j > i) yoxdursa ki, bu bina i-dən hündürdür.
Yuxarıdakı şəkildə mesaj alan binalar 2, 5, 6 və 9 olacaq.
Yalnız bir qüllə tikiləcək, lakin şəhər hökuməti hər biri fərqli hündürlüyə malik olan k qüllə variantı təklifi alıb (və tikinti dəyəri də fərqlidir). Təklif olunan qüllələr 1-dən k-ə qədər nömrələnir. Bu qüllələrin hər biri şəhərdəki bütün binaların hündürlüyündən də fərqlənən öz hündürlüyünə malikdir. Şəhər rəhbərləri hər bir təklif olunan k qüllə üçün mesaj alacaq maksimum bina sayını bilmək istəyirlər. Təbii ki, hesablamalar hər bir qüllənin optimal yerləşdirilməsi ilə aparılmalıdır.
Birinci sətir iki natural ədəd ehtiva edir: n (1 ≤ n ≤ 10^6) və k (1 ≤ k ≤ 10^5) - binaların sayı və təklif olunan qüllələrin sayı. İkinci sətir şəhərdəki binaların hündürlüklərini (1 ≤ hər bir bina və təklif olunan qüllənin hündürlüyü ≤ 10^9) ehtiva edən n natural ədəd ehtiva edir, nömrələnmiş ədədlər (birincidən n-ciyə qədər).
Üçüncü sətir k natural ədədindən ibarətdir - təklif olunan qüllələrin hündürlükləri.
Bir sətirdə k qeyri-mənfi tam ədəd çıxarın: üçüncü giriş sətirindəki hər bir qüllə üçün - qüllə optimal yerləşdirildikdə mesaj alacaq maksimum bina sayı.
Hər bir qüllənin optimal yerləşdirilməsi aşağıdakı şəkillərdə göstərilmişdir.
Nümunə 1