Rəqs edən fillər#2256
Dancing Elephants Pattayada möhtəşəm bir şoudur, burada fil bir cərgədə, səhnə adlanan düzülüşdə çıxış edir.
İllərlə təlim keçdikdən sonra fillər bir çox rəqs hərəkətlərinə yiyələniblər. Hər bir şou ardıcıl səhnələrdən ibarətdir və hər səhnədə bir fil rəqs hərəkəti edərək, mövqeyini dəyişə bilər.
Şou təşkilatçıları bütün şou boyunca filmlərin şəklini çəkməyi planlaşdırırlar. Onlar hər bir səhnədən sonra fillərin hamısının şəklini çəkəcəklər.
Şou zamanı istənilən anda bəzi fillər eyni mövqedə dayana bilər, yəni yan-yana dayanırlar.
Tək bir kamera fillərin qrupunu yalnız o zaman çəkə bilər ki, hamısı uzunluğunda bir seqmentin (hər iki sərhəd daxil olmaqla) daxilində yerləşsinlər. Fillər səhnə boyu səpələnə bilərlər, buna görə hamısını bir anda çəkmək üçün bir neçə kamera lazım ola bilər.
Məsələn, l = 10 və fillər , , , və mövqelərindədirsə, bir kamera bütün filləri çəkməyə bəs edir, aşağıda göstərildiyi kimi (fillər üçbucaq, kameralar trapets kimi verilib).
Növbəti səhnədə -də olan fil -yə keçir. Bundan sonra fillərin hamısını bir anda çəkmək üçün ən azı iki kamera lazımdır.
Daha sonra -da olan fil -yə keçir. Bu halda, bütün fillərin şəklini çəkmək üçün kamera lazımdır.
Sizin vəzifəniz hər səhnədən sonra bütün fillərin şəklini çəkmək üçün lazım olan minimum kamera sayını tapmaqdır.
Girişin ilk sətrində üç qeyri-mənfi tam ədəd , və (0 \leq n \leq 15 \cdot 10^4, 0 \leq l \leq 10^9, 0 \leq m \leq 15 \cdot 10^4) verilir.
Sonrakı sətrin hər birində bir tam ədəd x_i verilir, hərəsi bir filin mövqeyini göstərir (0 \leq x_i \leq 10^9). Bütün başlanğıc mövqelər artan sıradadır. Qeyd edək ki, rəqs zamanı fillərin ardıcıllığı dəyişə bilər.
Növbəti sətrin hər birində iki tam ədəd və verilir. Bu, müvafiq səhnədə -ci filin koordinatına keçdiyini göstərir. Zəmanət verilir ki, 0 \leq y \leq 10^9 şərtini ödəyir.
sətirdə, hər bir səhnədən sonra bütün fillərin şəklini çəkmək üçün lazım olan minimum kamera sayını çap edin.
Nümunə 1