Bulanıq şəkillər#9687
Deymon səyahətləri zamanı ziyarət etdiyi yerlərin şəkillərini çəkməyi çox sevir ki, sonra bu şəkilləri çərçivələrə yerləşdirə bilsin. Onun bütün şəkilləri n \times n piksel ölçüsündə kvadrat formatdadır. Parisə səyahət zamanı o, Eyfel qülləsi və Luvr kimi məşhur abidələrin bir çox gözəl şəkillərini çəkdi, lakin təəssüf ki, evə qayıtdıqda onun bütün şəkillərinin kənarlarının bulanıq olduğunu müəyyən etdi.
Yaxından baxdıqda. Deymon başa düşdü ki, bulanıq pikselləri «yaxşı» (yəni bulanıq olmayan) piksellərdən ayırmaq asandır. Daha ətraflı olaraq, bütün bulanıq olmayan piksellər belə bir xüsusiyyətə malik birləşdirilmiş sahə yaradır ki, iki bulanıq olmayan piksel arasında çəkilən istənilən üfüqi və ya şaquli xətt yalnız bulanıq olmayan piksellərdən keçir.
Uğursuz şəkillərindən maksimum dərs almaq üçün Deymon hər bir şəkildən bulanıq olmayan pikselləri içərisində saxlayan mümkün olan ən böyük şəkili kəsməyə qərar verir. Onun bütün çərçivələrinin kvadrat forması olduğuna görə, estetik səbəblərə görə kəsilmiş şəkil də kvadrat olmalıdır. Bundan əlavə, Deymon fotoların əyilməsini istəmir, buna görə kəsilmiş şəkilin tərəfləri ilkin şəkilin tərəflərinə paralel olmalıdır.
Birinci sətir piksel şəklində giriş şəklinin tərəfinin uzunluğu olan tam n~(n \le 10^5) ədədini təqdim edir;
Növbəti sətrin hər biri iki tam a_i və b_i~(0 \le a_i \le b_i < n) ədədini təqdim edir – -ci sətirdə ilk (a_i) və son (b_i) bulanıq olmayan piksellərin indeksləri.
Məlumdur ki:
Giriş şəkilinin hər bir sətirində və hər bir sütununda ən azı bir bulanıq olmayan piksel var.
Hər hansı iki qonşu sətirdə ən azı bir sütunda yerləşmiş ən azı iki bulanıq olmayan piksel var.
Vahid tam ədəd çap edin - şəkilin içərisində tamamilə bulanıq olmayan piksellərdən ibarət olan ən böyük kvadratın tərəfinin uzunluğu.
Nümunə 2
Nümunə 1