Pandoranın Qutusu#9065
Krat bərkərtirdi, Yunan allahı Aresi məğlub etmək üçün Pandoranın Ölçüsüz Güc Qutusunu əldə etməlidir. Bu güclü artefakt dərin qədim bir dərədə gizlənmiş Pandoranın Məbədi yolu ilə əldə edilir. Məscid yolunda Kratosun dağını aşması lazımdır, -ci dağın hündürlüyü a_i metrdir.
Hətta böyük Kratosun da qorxduğu bir nəsnə var — hündürlük. O, heç vaxt aşağıya tullanmır: kəskin enmələr Spartalıya qorxu gətirir. Lakin onun bir ilahi hədiyyəsi var — əgər a_i = a_j olsa, bir hərəkətlə -dən -yə qədər olan bütün dağların hündürlüyünü bərabərləşdirə bilər. Bu gücü tətbiq etdikdən sonra -dən -yə (daxil olmaqla) qədər olan bütün dağlar hündürlüyü a_i olur.
Məbədə çatmaq üçün Kratos gücünü istifadə etməlidir ki, yolda hündürlük azalmadan sabit qalsın, yəni i = 1, 2, ..., n - 1 üçün a_i \le a_{i+1} şərti yerinə yetirilsin.
Kratos tələsir və Aresin diqqətini cəlb etmək istəmir, buna görə də o, gücünü mümkün olan ən az sayda tətbiq etməlidir. Spartala məqsədinə çatmaqda kömək edin və minimal bərabərləşdirmələrin sayını tapın.
Birinci sətirdə Məbədə gedən yolda dağların sayı n~(1 \le n \le 10^6) verilmişdir.
İkinci sətirdə dağların hündürlükləri olan tam ədədi a_i~(1 \le a_i \le 10^6) verilmişdir.
İlk sətirdə yolu sabit etmək üçün Kratosun edəcəyi minimal hərəkətlərin sayı -də çıxarılır.
Sonra sətirdə iki ədəd çıxarılır — Kratosun bərabərləşdirməli olduğu intervalların sərhədləri və r~(1 \le l \le r \le n).
Hərəkətlər Kratosun onları icra etməli olduğu ardıcıllıqla çıxarılmalıdır.
Əgər həll olmadıqda, çıxarın.
Nümunə 1
Nümunə 2